[백준] 1987 알파벳 - 골드 4

[오늘의 문제]

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

---

[오늘의 학습 키워드]

• DFS, 백트래킹

---

1. 문제 설명

 

R x C 크기의 보드에 알파벳이 입력되어 있습니다.

 

알파벳은 대문자이고 좌상단 부터 탐색을 시작해서 인접한 4칸 중 한칸으로 이동하는데 새로 이동한 칸에 적힌 알파벳이 지금까지 지나온 알파벳 과 달라야 합니다.

 

즉 새로운 알파벳을 찾아서 이동 가능한 최장거리를 구하는 문제입니다.

---

[제한사항]

• 시간 제한 2초
• 메모리 제한 256MB
• 1 ≤ R, C ≤ 20

---

2. 접근 방식

 

DFS를 이용해 백트래킹을 실시하면 될 것 같습니다.

 

알파벳을 최대 26개의 문자이니 알파벳의 사용 여부를 확인할 딕셔너리를 만들고 현재 보드에 적힌 알파벳이 딕셔너리에서 사용 가능한지를 확인한 다음 모든 경우의 수를 구해주면 될 것 같습니다.

 

그러다 더이상 이동이 불가능한 지점을 만나면 현재 이동한 거리와 정답 중 더 큰 값으로 바꾸고 종료해서 모든 경우의 수를 구해주면 될 것 같습니다.

 

---

3. 코드

import sys
input = sys.stdin.readline

dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

def DFS(x, y, count, alphabets):
    global answer

    # 인접한 4방향 탐색
    for k in range(4):
        nx = x + dx[k]
        ny = y + dy[k]

        # board 안에 있는데 다음 위치가 사용하지 않은 알파벳인 경우
        if 0 <= nx < R and 0 <= ny < C:
            if alphabets[board[nx][ny]] == True:
                alphabets[board[nx][ny]] = False
                DFS(nx, ny, count + 1, alphabets)   # 깊이 우선 탐색
                alphabets[board[nx][ny]] = True     # 모든 경우의 수 찾기 위해 초기화
    # 더이상 이동이 불가능한 경우 정답 업데이트
    else:
        answer = max(answer, count)
        return

# 입력
R, C = map(int, input().split())
board = [list(input()) for _ in range(R)]

# 알파벳 사용 여부를 확인할 딕셔너리
alphabet_dict = {
    "A" : True, "B" : True, "C" : True, "D" : True, "E" : True, "F" : True, "G" : True, 
    "H" : True, "I" : True, "J" : True, "K" : True, "L" : True, "M" : True, "N" : True, 
    "O" : True, "P" : True, "Q" : True, "R" : True, "S" : True, "T" : True, "U" : True, 
    "V" : True, "W" : True, "X" : True, "Y" : True, "Z" : True,
}

# DFS 탐색 시작
alphabet_dict[board[0][0]] = False
answer = 0
DFS(0, 0, 1, alphabet_dict)
print(answer)

 

---

[코드 설명]

# 입력
R, C = map(int, input().split())
board = [list(input()) for _ in range(R)]

# 알파벳 사용 여부를 확인할 딕셔너리
alphabet_dict = {
    "A" : True, "B" : True, "C" : True, "D" : True, "E" : True, "F" : True, "G" : True, 
    "H" : True, "I" : True, "J" : True, "K" : True, "L" : True, "M" : True, "N" : True, 
    "O" : True, "P" : True, "Q" : True, "R" : True, "S" : True, "T" : True, "U" : True, 
    "V" : True, "W" : True, "X" : True, "Y" : True, "Z" : True,
}

# DFS 탐색 시작
alphabet_dict[board[0][0]] = False
answer = 0
DFS(0, 0, 1, alphabet_dict)
print(answer)

 

입력을 받고 알파벳 딕셔너리를 생성해 주었습니다.

 

딕셔너리를 선택한 이유는 해시 테이블 자료구조이기 때문에 삽입, 삭제 과정이 O(1)로 매우 빠르게 동작해서 입니다.

 

다른 사람들의 경우 ord를 사용해 문자 번호를 이용해 중복여부를 확인하던데 저는 딕셔너리를 사용했습니다.

 

첫 시작위치인 board의 0, 0 위치의 값의 알파벳을 사용여부 처리하고 DFS 탐색을 시작합니다.

---

dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

def DFS(x, y, count, alphabets):
    global answer

    # 인접한 4방향 탐색
    for k in range(4):
        nx = x + dx[k]
        ny = y + dy[k]

        # board 안에 있는데 다음 위치가 사용하지 않은 알파벳인 경우
        if 0 <= nx < R and 0 <= ny < C:
            if alphabets[board[nx][ny]] == True:
                alphabets[board[nx][ny]] = False
                DFS(nx, ny, count + 1, alphabets)   # 깊이 우선 탐색
                alphabets[board[nx][ny]] = True     # 모든 경우의 수 찾기 위해 초기화
    # 더이상 이동이 불가능한 경우 정답 업데이트
    else:
        answer = max(answer, count)
        return

 

4방향 탐색을 실시하는데 조건에 맞춰 4방향 탐색을 실시합니다.

 

1. board의 밖을 벗어나면 안됩니다.

 

2. 다음 board 위치의 알파벳이 이전까지 사용한 적이 없어야 합니다.

 

이 경우를 찾아 DFS의 깊이 우선 탐색을 실시합니다.

 

그러다 for - else 조건에 의해 4방향 탐색이 불가능한 경우

 

즉, 더이상 탐색이 불가능한 경우는 최대 depth를 탐색한 경우이니 이때 정답을 업데이트 하고 종료합니다.

 

백트래킹을 활용해 모든 경우의 수를 구하기 위해선 이전 깊이에서 사용한 조건을 초기화 해주어야 하니 알파벳을 다시 사용 가능으로 바꿔 주었습니다.

---

4. 결과

---

[회고]

 

이번 문제는 해결하는 과정에서 가지치기를 더 했어야 했는데 더이상 조건이 생각나지 않았습니다.

 

우선 Python3 로 해결하기에는 문제 자체가 너무 조건이 빡빡한 문제 였습니다.

 

깊이 우선 탐색의 경우 원래도 시간이 많이 걸리는데 Python3로 하기에는 동작과정이 많아 시간이 오래 걸립니다.

 

결국 PyPy로 해결할 수 밖에 없는데 그 마저도 처음에는 visted 배열을 사용하여 시간초과가 발생했습니다.

 

DFS 깊이 우선 탐색의 경우 visited 배열이 크게 필요가 없었습니다.

 

왜냐하면 모든 경우의 수를 찾아야 하고 어차피 중복 여부는 알파벳에서 한번 걸러주기 때문이었습니다.

 

다음 탐색위치가 알파벳에 걸린다면 어차피 그쪽으로는 탐색을 하지 않기 때문입니다.

 

visited를 없애주고 조건을 수정해서 겨우 해결이 가능했습니다.

 

다른 분들의 코드를 참고하니 결국 알파벳은 26개 뿐이라 result의 길이가 26이 되면 무조건 종료되게 하였습니다.

 

생각해보면 당연한 것이었습니다. 그러나 제 코드에 적용하기에는 아직 코딩 실력이 부족하여서... 코테에서 이런 문제가 나오지 않길 바래야 할 것 같습니다...

 

그래도 이번 문제를 해결하며 DFS 와 백트래킹에 대해서 제대로 감을 잡았고 그래프 탐색 이론 실력이 상승한 것 같습니다.