알파벳

출처 : 백준 #1987

시간 제한	메모리 제한
2초	256MB

---

문제

세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다.

말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다.

좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 프로그램을 작성하시오. 말이 지나는 칸은 좌측 상단의 칸도 포함된다.

---

입력

첫째 줄에 R과 C가 빈칸을 사이에 두고 주어진다. (1 ≤ R,C ≤ 20) 둘째 줄부터 R개의 줄에 걸쳐서 보드에 적혀 있는 C개의 대문자 알파벳들이 빈칸 없이 주어진다.

---

출력

첫째 줄에 말이 지날 수 있는 최대의 칸 수를 출력한다.

---

입출력 예시

예제 입력 1

2 4
CAAB
ADCB

예제 출력 1

3

---

예제 입력 2

3 6
HFDFFB
AJHGDH
DGAGEH

예제 출력 2

6

---

예제 입력 3

5 5
IEFCJ
FHFKC
FFALF
HFGCF
HMCHH

예제 출력 3

10

---

풀이

생각 및 풀이 설명

• DFS로 처음에 접근하였다.

  • recursion을 이용하기 때문에 알파벳 방문 여부를 담은 리스트 alpha와 현재 문자열을 담고 있는 now를 파라미터로 넣어주었다.
  • 만약 더이상 방문할 것이 없다면 return하고, 알파벳 총 개수인 26개를 모두 방문하더라도 return이 된다.
  • Python3로는 시간초과가 떴고, Pypy3로는 통과가 되었는데 그 이유는 recursion을 계속 하게 되면서 최악의 경우O((NM)^2)의 시간 복잡도가 걸린다.(핵심 : 함수의 호출 횟수가 최악의 경우 엄청 커지기 때문)
  • Pypy3라도 통과할 수 있었던 이유는 알파벳 26개를 모두 방문하면 return 하는 부분과 1차원 배열을 탐색함으로써 이미 방문한 alphabet의 탐색을 O(1)로 줄였기 때문이다.

• BFS로 접근하는 방식은 위의 DFS 접근방식과 크게 다르지 않다.

  • 방문을 체크하지 않아도 통과할 수 있었던 이유는 큐를 집합으로 구성했기 때문이다. (중복이 제거되고, 원소 추출이 O(1)의 시간으로 가능함)
  • 큐를 집합으로 하지않고 deque를 통해 구성하면 시간초과가 나온다.(중복되는 원소가 많이 들어가기 떄문)
  • 앞으로 이 문제를 통해 집합 자료구조를 조금 더 활용해 볼 수 있는 기회가 되었다.

python code (Pypy3 - DFS)

# 백준 1987번 알파벳(DFS)
from sys import stdin
import copy
input = stdin.readline
n, m = map(int, input().split())
matrix = []
for _ in range(n):
    matrix.append(input().rstrip())

# 동, 남, 서, 북
dx = [0, +1, 0, -1]
dy = [+1, 0, -1, 0]
alpha = [False]*26
alpha[ord(matrix[0][0]) - 65] = True
answer = 0
def dfs(x, y, now, alpha):
    global answer
    answer = max(answer, len(now))
    if answer == 26:        # 모든 알파벳을 돌면 26개가 됨
        return
    for i in range(4):
        temp_x = x + dx[i]
        temp_y = y + dy[i]
        if 0 <= temp_x < n and 0 <= temp_y < m:    # 범위 확인
            # if matrix[temp_x][temp_y] not in now:  # 문자열 확인(이게 시간초과의 이유?)
            temp = ord(matrix[temp_x][temp_y]) - 65
            if alpha[temp] == False:
                alpha[temp] = True
                # print(now+matrix[temp_x][temp_y])
                dfs(temp_x, temp_y, now+matrix[temp_x][temp_y], alpha)
                alpha[temp] = False
    return

dfs(0, 0, matrix[0][0], alpha)
print(answer)

Python code (python3 - BFS)

# 백준 1987번 알파벳(BFS)
from sys import stdin
from collections import deque
import copy
input = stdin.readline
n, m = map(int, input().split())
matrix = []
for _ in range(n):
    matrix.append(input().rstrip())

# 동, 남, 서, 북
dx = [0, +1, 0, -1]
dy = [+1, 0, -1, 0]
q = set()
q.add((0, 0, matrix[0][0]))
answer = 0
def bfs(q):
    global answer
    while q:
        x, y, sentence = q.popleft()
        answer = max(answer, len(sentence))
        if answer == 26:        # 모든 알파벳을 돌면 26개가 됨
            return
        for i in range(4):
            temp_x = x + dx[i]
            temp_y = y + dy[i]
            if 0 <= temp_x < n and 0<= temp_y < m:
                if matrix[temp_x][temp_y] not in sentence:
                    q.add((temp_x, temp_y, sentence + matrix[temp_x][temp_y]))
    return
bfs(q)
print(answer)