[boj] 알파벳_1987

# 알파벳 https://www.acmicpc.net/problem/1987
import sys
from string import ascii_uppercase
sys.setrecursionlimit(10000)

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

graph = []
rest = list(ascii_uppercase)
count = 0
max_count = 0

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

for _ in range(R):
    read = sys.stdin.readline().rstrip()
    graph.append(read)

def Search(par_x, par_y):
    global count
    global max_count

    count += 1
    if count > max_count:
        max_count = count

    for i in range(4):
        new_x = par_x + dx[i]
        new_y = par_y + dy[i]

        if new_x <= -1 or new_y <= -1 or new_x >= R or new_y >= C:
            continue
        if graph[new_x][new_y] not in rest:
            continue

        temp_idx = rest.index(graph[new_x][new_y])
        del rest[temp_idx]

        Search(new_x, new_y)
        rest.append(graph[new_x][new_y])

    count -= 1

first = graph[0][0]
rest.remove(first)
Search(0, 0)
print(max_count)

백트래킹이 더해진 DFS 로 해결한 문제이다.

 

처음에는 백트래킹 생각을 못하고 오직 DFS로 해결하기 위해 방문한 알파벳을 외부 리스트에 추가하고, 매 재귀가 일어날 때마다 해당 리스트를 검사하는 방식으로 구현을 시도했었는데, 두가지 큰 문제가 있었다.

 

1. 상, 하, 좌, 우 순서로 노드를 방문하게 되면 노드의 방문 순서에 따라 외부 리스트에 방문한 알파벳이 추가되는 순서가 바뀌게 되어 결과가 다르게 출력되는 문제가 생겼다.

 

2. 파이썬으로 제출하니 실행속도가 너무 느렸다.

 

첫번째 문제를 해결하기 위해 백트래킹을 추가해야 했는데, 백트래킹이란 것은 전혀 들어보지 못했었기 때문에 따로 공부를 해야 했었다.

 

두번째 문제를 해결하기 위해 함수 내부 for 루프에서 4개의 모든 인접 노드를 방문 시도하는 것이 아닌 조건에 맞는 노드만 방문하게 하였으며, 노드 방문 후 길이 막혀 스택이 반환될 때 방문했던 알파벳을 다시 반환하게 하여 이전 노드에서도 인접한 동일한 알파벳을 방문할 수 있도록 구현했다. 이렇게 함수가 반환될 때 알파벳을 다시 반환하게 하는 작업을 백트래킹이라고 한다.

글로 보면 무지하게 이해하기 어렵다 ㅠㅠ

 

여담이지만 같이 스터디를 하는 스터디원들은 너무 쉽게 풀었다고 해서 조금 슬펐다. 그래도 DFS를 구현하며 필요한 노드만을 방문하게 하는 방법과, 간단하게 나마 백트래킹을 구현한 점에서 이전보다 더 발전했다고 생각하고 싶다.