BOJ 1706 - 크로스워드 (Python)

S2, 문자열

문제 설명

동혁이는 크로스워드 퍼즐을 좋아한다. R×C 크기의 크로스워드 퍼즐을 생각해 보자. 이 퍼즐은 R×C 크기의 표로 이루어지는데, 퍼즐을 다 풀면 금지된 칸을 제외하고는 각 칸에 알파벳이 하나씩 적혀 있게 된다. 아래는 R = 5, C = 5 인 경우 다 푼 퍼즐의 한 예이다. 검은 칸은 금지된 칸이다.

세로 또는 가로로 연속되어 있고, 더 이상 확장될 수 없는 낱말이 퍼즐 내에 존재하는 단어가 된다. 위의 퍼즐과 같은 경우, 가로 낱말은 good, an, messy, it, late의 5개가 있고, 세로 낱말은 game, one, sit, byte의 4개가 있다. 이 중 사전식 순으로 가장 앞서 있는 낱말은 an이다.

다 푼 퍼즐이 주어졌을 때, 퍼즐 내에 존재하는 모든 낱말 중 사전식 순으로 가장 앞서 있는 낱말을 구하는 프로그램을 작성하시오.

입력

첫째 줄에는 퍼즐의 R과 C가 빈 칸을 사이에 두고 주어진다. (2 ≤ R, C ≤ 20) 이어서 R개의 줄에 걸쳐 다 푼 퍼즐이 주어진다. 각 줄은 C개의 알파벳 소문자 또는 금지된 칸을 나타내는 #로 이루어진다. 낱말이 하나 이상 있는 입력만 주어진다.

출력

첫째 줄에 사전식 순으로 가장 앞서 있는 낱말을 출력한다.

입력 예시

4 5
adaca
da##b
abb#b
abbac

출력 예시

abb

풀이

1. row 기준으로 먼저 문자열들을 확인한다.
2. #을 만날 때 까지 문자들을 더해가면서 만들어진 문자열을 words 리스트에 추가한다.
3. col 기준으로 문자열들을 확인한다.

# 크로스워드, S2

from sys import stdin

n, m = map(int, stdin.readline().split())
board = [[] for _ in range(n)]
for i in range(n):
    board[i] = stdin.readline().rstrip()

words = []

for i in range(n):
    tmp = ''
    for j in range(m):
        if board[i][j] == '#':
            if len(tmp) > 1:
                words.append(tmp)
            tmp = ''
        else:
            tmp += board[i][j]

    if len(tmp) > 1:
        words.append(tmp)

for j in range(m):
    tmp = ''
    for i in range(n):
        if board[i][j] == '#':
            if len(tmp) > 1:
                words.append(tmp)
            tmp = ''
        else:
            tmp += board[i][j]

    if len(tmp) > 1:
        words.append(tmp)

print(sorted(words)[0])