[백준 Python] 3005번 크로스워드 퍼즐 쳐다보기

백준 3005 크로스워드 퍼즐 쳐다보기 (실버 2)

문제

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

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

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

입력

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

출력

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

풀이 및 회고

풀이

모든 원소를 전부 돌아다니면서 해당 위치가 단어의 시작 조건에 부합하는 경우를 우선 판단한다. 조건으로는 이전에 원소가 존재하지 않거나 이전에 '#'이 존재하는 경우이다. 해당 조건을 만족하는 경우 단어를 탐색하기 시작하며, 탐색이 끝난 후에 단어의 길이가 2이상일 경우 기존의 결과와 사전적 순위를 비교하여 결과를 업데이트한다. 이때 비교에는 파이썬의 min함수를 사용하며 결과의 첫 값은 '{'이다.(유니코드 123번에 해당하며 알파벳 중 가장 높은 'z'가 122이다)

회고

구현 문제였지만 나름 재미있었다. 구현 문제를 가장 싫어하지만 문제를 보자마자 풀이가 보이기도 했고 예외적 상황도 한번에 보여서 쉬웠던 것 같다. 그러나 여전히 코드를 막 쓰고도 굳이 고치고 싶지 않다.. 구현문제가 그렇지 뭐.. 아 이 문제는 실버 2까지는 아닌 것 같아서 기여에 실버 3을 적을 예정이다.

코드

r, c = map(int, input().split())
board = [list(input()) for _ in range(r)]
result = "{"  # Unicode: 123 (z: 122)
for i in range(r):
    for j in range(c):
        if i == 0 or board[i - 1][j] == "#":
            row_idx = i
            row_result = ""
            while row_idx < r:
                if board[row_idx][j] == "#":
                    break
                row_result += board[row_idx][j]
                row_idx += 1
            if len(row_result) > 1:
                result = min(result, row_result)
        if j == 0 or board[i][j - 1] == "#":
            col_idx = j
            col_result = ""
            while col_idx < c:
                if board[i][col_idx] == "#":
                    break
                col_result += board[i][col_idx]
                col_idx += 1
            if len(col_result) > 1:
                result = min(result, col_result)
print(result)

>> iwtkmn0219의 Github <<