dfs 문제 특징

• 시작점부터 끝점까지의 경로를 기억, 누적할 필요가 있다.
• return 값을 사용하여 재귀적으로 표현하기가 익숙치 않다.

백준 2문제를 참고로 정리하자.

알파벳

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

다양한 크기의 보드에 말판이 올라가 있다. 보드는 격자 무늬로 나누어져 있으며 각 칸마다 알파벳이 적혀있다. 지나온 경로에서 없는 알파벳만을 밟으며 이동할 수 있는 최대 거리를 찾자.

트리의 지름

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

트리 안의 서로 다른 두 점의 경로 중 가장 긴 것을 트리의 지름이라 한다. 이 때, 간선 간에는 다양한 가중치 값이 존재한다.

알파벳 참고 코드

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

arr = [list(input()) for _ in range(R)]
check = [[0]*C for _ in range(R)]

A = ord('A')
stack = [(0,0,1,1<<(ord(arr[0][0])-A))]
result = 0
dx = [-1,1,0,0]
dy = [0,0,1,-1]
while stack:
    x,y,cnt,total = stack.pop()
    if result < cnt:
        result = cnt
    if result == 26:
        break
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < R and 0<= ny <C:
            if (total & (1<<ord(arr[nx][ny])- A)) == 0:
                temp = total | (1<<(ord(arr[nx][ny])-A))
                if check[nx][ny] != temp:
                    check[nx][ny] = temp
                    stack.append((nx,ny,cnt+1,temp))
print(result)

from sys import stdin


input = stdin.readline


def solve():

    R, C = map(int, input().split())
    length = R * C
    visited = [set() for _ in range(length)]

    arr = [0] * length
    for i in range(R):
        arr[i * C:(i+1) * C] = [*map(lambda char: 1 << (ord(char) - 65), input()[:-1])]

    ans = 0
    que = {0}
    visited[0].add(arr[0])
    for k in range(27):
        if k == 26 or not que:
            ans = k
            break
        new_que = set()
        new_visited = [set() for _ in range(length)]
        while que:
            cur_pos = que.pop()
            i, j = cur_pos // C, cur_pos % C
            adj = []
            if i > 0: adj.append(cur_pos-C)
            if j > 0: adj.append(cur_pos-1)
            if i < R - 1: adj.append(cur_pos+C)
            if j < C - 1: adj.append(cur_pos+1)
            for neighbor_pos in adj:
                neighbor_alpha = arr[neighbor_pos]
                flag = True
                for visited_alpha in visited[cur_pos]:
                    if not neighbor_alpha & visited_alpha:
                        new_visited[neighbor_pos].add(visited_alpha | neighbor_alpha)
                        if flag:
                            new_que.add(neighbor_pos)
                            flag = False

        que = new_que
        visited = new_visited

    return ans


if __name__ == '__main__':
    print(solve())

참고 코드 분석

• 비트를 이용하여 경로를 저장하였다. 2^0은 'A'와 2^1은 'B'와 매칭시켰다. 경로의 저장을 한 정수로 표현하여 메모리 절약과 비트 비교연산으로 실행 시간을 줄일 수 있다.
• 2번째 참고 코드에서, 최대 반복 횟수만큼만 loop를 돌리기 위해서 new_que를 선언하였다.
• 첫 번째 참고 코드에서 check list를 통해 한 노드에서 중복된 경로의 연산을 피하도록 했다.

트리의 지름 참고 코드

import sys

def dfs(x):
    visited = [-1] * (N+1)
    visited[x] = 0
    q = [x]
    while q:
        now = q.pop()
        for i, cost in tree[now]:
            if visited[i] == -1:
                visited[i] = visited[now] + cost
                q.append(i)
    return visited

def main():
    global tree, N
    I = sys.stdin.readline
    N = int(I())
    tree = [[] for _ in range(N+1)]
    for _ in range(N-1):
        a, b, c = map(int,I().split())
        tree[a].append((b, c))
        tree[b].append((a, c))
    res1 = bfs(1)
    idx = res1.index(max(res1))
    print(max(bfs(idx)))

if __name__ == "__main__":
    main()

트리의 지름 참고 코드 분석

• 트리의 지름을 구하기 위해서 leaf list를 구하고 한 leaf로부터 다른 leaf까지의 경로를 모두 구해서 가장 긴 경로를 트리의 지름으로 했다. 트리의 특성을 이용하면 참고 코드와 같이 루트 노드에서 출발해 leaf까지의 길이를 구하고 가장 긴 길이의 leaf에서 dfs를 하는 것으로 간단하게 할 수 있다.

마무리

dfs로만 풀 수 있는 문제의 특징에서 다음의 것을 정리하자.

recursive 구현 vs list 구현

우선 function object가 call stack에서 얼마나 많은 메모리를 할당받는 지 모른다. 컴퓨터 구조와도 연관이 있어서 나중에 알아봐야겠다. 참고 코드 모두 list를 이용해 pop, append로 구현했으므로 list 구현 쪽으로 바꾸는 것이 좋을 듯 싶다. 다른 차이는 잘 모르겠다.

경로의 누적, 특징을 어떻게 구현할까

알파벳 문제의 경우, 비트를 이용해서 search의 시간을 대폭 줄였다. 트리의 지름 문제의 경우, 트리의 특성을 이용해서 dfs 호출을 최소화하였다. 아직 명확하게 dfs를 이해했다고 할 수 없어서 더 풀어볼까 한다.