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

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

 

코드

r, c = map(int, input().split())
cp = [input() for _ in range(r)]

dir = [(-1, 0), (0, 1), (1, 0), (0, -1)]

words = set()
for i in range(r):  # 행
    for j in range(c):  # 열
        # 세로
        if (i == 0 or cp[i-1][j] == '#') and cp[i][j] != '#':
            rr = i
            word = ""
            while rr < r and cp[rr][j] != '#':
                word += cp[rr][j]
                rr += 1
            if len(word) >= 2:
                words.add(word)
        # 가로
        if (j == 0 or cp[i][j-1] == '#') and cp[i][j] != '#':
            cc = j
            word = ""
            while cc < c and cp[i][cc] != '#':
                word += cp[i][cc]
                cc += 1
            if len(word) >= 2:
                words.add(word)
print(sorted(list(words))[0])

 

이 문제는 가로(왼쪽->오른쪽)과 세로(위->아래)로 읽을 수 있는 단어만 확인하면 된다. 그리고 단어의 길이도 퍼즐의 끝에 도달하거나 '#'이 나오기 전까지 나오는 알파벳은 모두 포함한 길이이다.

 

그렇기 때문에 퍼즐의 각 칸을 순회하며 해당 칸에서 시작하여 가로, 세로로 2글자 이상 단어를 만들 수 있다면 집합 words에 추가하도록 하였다. 이때 어떤 칸에서 시작한다는 것은 그 칸이 퍼즐의 가장자리에 있는 칸이거나 가로라면 왼쪽, 세로라면 위쪽에 있는 칸이 '#'인 경우를 말한다.