[baekjoon] 1706번 크로스워드

출처

---

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

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개의 알파벳 소문자 또는 금지된 칸을 나타내는 #로 이루어진다.

낱말이 하나 이상 있는 입력만 주어진다.

 

 

출력

---

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

 

 

풀이 및 코드

---

문제 조건대로 따라 구현만 하면 되는 문제이다.

퍼즐의 크기 RxC (2 ≤ R, C ≤ 20) 이 크지 않기 때문에 시간, 메모리 제한은 넉넉했다.

 

1. forloop로 row, column별로 각각 단어들을 한줄씩 읽어 들인 후, '#'를 기준으로 파싱한다.
2. 파싱한 것들을 forloop로 확인하며, 연속되지 않은(길이가 1인)것은 제외하고 나머지는 낱말로 간주한다.
3. row, column별로 나온 모든 낱말들을 사전순으로 정렬하고 맨 앞 값을 출력한다.

 

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

words = []

for row_word in cross_word:
	# '#'을 기준으로 파싱
    parsing = row_word.split('#')
    for p in parsing:
        # 길이가 2이상이어야 낱말로 간주
        if len(p) >= 2:
            words.append(p)

for i in range(c):
    column_word = ''
    for word in cross_word:
        column_word += word[i]
    # '#'을 기준으로 파싱
    parsing = column_word.split('#')
    for p in parsing:
        # 길이가 2이상이어야 낱말로 간주
        if len(p) >= 2:
            words.append(p)

# 사전순 정렬
words.sort()
print(words[0])