[파이썬/python] 백준 1706 - 크로스워드

문제

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

---

문제 설명

1.   RxC 크기의 다 푼 크로스워드 퍼즐이 입력된다.
   1. 각 칸은 알파벳이 하나씩 적혀있다.
   2. 금지된 칸은 #으로 표기한다. 
2. 각 가로, 세로별 존재하는 낱말 중사전식으로 가장 앞서 있는 낱말을 구해라.
   1. 이 때 한 단어는 낱말로 취급하지 않는다.

 

---

풀이 

1. 완전탐색을 통해 가로 세로 별로 낱말을 탐색한다.
2. 금지 단어 #을 기준으로 낱말을 파싱하여 한 글자가 아니라면 최종 단어 배열에 추가한다. 
3. 정렬을 통해 가장 첫 번째 인덱스 단어를 출력한다.

---

코드

import sys
input = sys.stdin.readline

R,C = map(int,input().split())

board = [list(input().strip())+["#"] for _ in range(R) ]
board.append(['#' for _ in range(C)])
words = []

#가로 단어 검사
for row in range(R):
    word = []
    for col in range(C+1):
        if board[row][col] == '#':
            if len(word) > 1:
                words.append("".join(word))
            word.clear()
        else:
            word.append(board[row][col])
#세로 단어 검사
for col in range(C):
    word = []
    for row in range(R+1):
        if board[row][col] == '#':
            if len(word) > 1:
                words.append("".join(word))
            word.clear()
        else:
            word.append(board[row][col])

print(sorted(words)[0])

---

시간복잡도

• 최악일 경우 $R, C = 20$
• 가로 탐색 시 시간복잡도 : $O(R*C)$
• 세로 탐색 시 시간복잡도 : $O(R*C)$
• 총 시간복잡도 : $O(2*R*C)$ = $(8*10^2)$