[백준, python] 1706번 - 크로스워드

백준 문제풀이 시작

---

문제

동혁이는 크로스워드 퍼즐을 좋아한다.
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개의 알파벳 소문자 또는 금지된 칸을 나타내는 #로 이루어진다. 낱말이 하나 이상 있는 입력만 주어진다.

출력

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

---

풀이

풀이 확인하기

이번 문제는 조건에 알맞는 문자열을 찾을 수 있도록 분기를 잘 해줘야 한다. 입력받은 크로스워드를 이차원 배열로 담고, 가로로 된 단어를 찾는 이중 반복문을 한번, 세로로 찾는 이중 반복문을 한번, 총 두번의 반복문을 돌린다. 반복문으로 순회하다가 #을 만난다면 지금까지 읽은 단어가 1글자보다 크다면 단어 리스트에 추가하고 아닐 경우 추가하지 않는다.(한글자는 단어가 아니기 때문.)
순회가 전부 끝나고 단어가 모였다면 정렬 후 첫번째 값을 출력한다.

import sys
input = sys.stdin.readline

width, height = map(int, input().split())

lis = [[]for _ in range(width)]

for i in range(width):
    a = list(input().strip())
    lis[i] = a

words = []

for i in range(width):
    word = ""
    for j in range(height):
        if lis[i][j] == "#":
            if len(word) > 1:
                words.append(word)
            word = ""
        elif j == height-1 and lis[i][j] != "#":
            word += lis[i][j]
            if len(word) > 1:
                words.append(word)
        else:
            word += lis[i][j]

for i in range(height):
    word = ""
    for j in range(width):
        if lis[j][i] == "#":
            if len(word) > 1:
                words.append(word)
            word = ""
        elif j == width-1 and lis[j][i] != "#":
            word += lis[j][i]
            if len(word) > 1:
                words.append(word)
        else:
            word += lis[j][i]

words.sort()
print(words[0])

• baekjoon
• python