[백준 3005번] 크로스워드 퍼즐 쳐다보기 파이썬 풀이

 

크로스워드 퍼즐 쳐다보기 

1 초

128 MB

1260

702

603

57.538%

문제

크로스워드 퍼즐은 R*C크기의 직사각형으로 이루어져 있고, 각 칸은 비어있거나 막혀있다. 퍼즐은 가로(왼쪽->오른쪽) 또는 세로(위->아래)로 연속된 빈 칸에 단어를 채우면서 푼다.

동혁이는 크로스워드 퍼즐을 풀지 않는다. 그는 풀려있는 퍼즐을 쳐다본다. 그런 후에, 그는 그 퍼즐에서 사전순으로 제일 앞서는 단어를 찾는다. (단어는 적어도 2글자이다.)

크로스워드 퍼즐이 주어졌을 때, 사전순으로 제일 앞서는 단어를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 R과 C (2 ≤ R, C ≤ 20)가 주어진다. R는 행의 개수, C는 열의 개수이다. 그 다음 R개의 줄엔 C개의 문자가 포함되어 있다. 각 문자는 영어 알파벳 소문자 또는 '#'이며, '#'인 경우에는 막혀있는 것이다.

출력

첫째 줄에 사전순으로 제일 앞서는 단어를 출력한다. 정답이 항상 존재하는 경우만 입력으로 주어진다.

예제 입력 1

4 4
luka
o#a#
kula
i#a#

예제 출력 1 

kala

예제 입력 2 

4 4
luka
o#a#
kula
i#as

예제 출력 2

as

예제 입력 3

4 5
adaca
da##b
abb#b
abbac

예제 출력 3

abb

 

구현, 문자열 문제이다.

 

이 문제를 해결하기 위해 내가 생각한 알고리즘은 아래와 같다.

 

1. 빈 배열을 준비한다.

2. 2차원 배열이므로 2중 반복문을 돌면서 각 문자에 대해 탐색한다.

    2.1. 빈 문자열을 만들고 '#'인지 아니라면 문자열에 합한다.
    2.2. 만약 '#'을 만난다면 지금까지 만든 문자열을 배열에 삽입하고 2.1번으로 되돌아간다.

3. 가로와 세로 모든 줄에 대해 탐색을 완료하였다면 배열을 정렬하고, 첫번째 문자를 출력한다.

# https://www.acmicpc.net/problem/3005
'''
'#' 을 만나기전까지 돌면서, 문자 만들고 만들어진 글자가 2글자 이상이라면 words에 삽입
words 배열을 정렬한 뒤, 첫번재 문자 출력
'''
r,c = map(int,input().split())
words = []
data = [list(input()) for _ in range(r)]
# 가로로 만들 수 있는 문자 삽입
for i in range(r):
    word = ''
    for j in range(c):
        if data[i][j] != '#':
            word += data[i][j] # '#'이 아니라면 더하기
        else: # '#'을 만난경우 만들어진 문자가 2글자 이상인지 검사
            # 2글자 이상이라면 words에 삽입
            if len(word) >= 2:
                words.append(word)
            word = '' # word 초기
    if len(word) >= 2:
        words.append(word)
# 세로로 만들 수 있는 문자 삽입
for i in range(c):
    word = ''
    for j in range(r):
        if data[j][i] != '#':
            word += data[j][i] # '#'이 아니라면 더하기
        else: # '#'을 만난경우 만들어진 문자가 2글자 이상인지 검사
            # 2글자 이상이라면 words에 삽입
            if len(word) >= 2:
                words.append(word)
            word = '' # word 초기
    if len(word) >= 2:
        words.append(word)

# 정렬했을때 가장 먼저 오는 문자 출력
print(sorted(words)[0])

 

https://www.acmicpc.net/problem/3005

3005번: 크로스워드 퍼즐 쳐다보기