99클럽 코테 스터디 8일차 TIL / DFS(깊이 우선 탐색)

✏️ 문제

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

 

우리 나라는 가족 혹은 친척들 사이의 관계를 촌수라는 단위로 표현하는 독특한 문화를 가지고 있다. 이러한 촌수는 다음과 같은 방식으로 계산된다. 기본적으로 부모와 자식 사이를 1촌으로 정의하고 이로부터 사람들 간의 촌수를 계산한다. 예를 들면 나와 아버지, 아버지와 할아버지는 각각 1촌으로 나와 할아버지는 2촌이 되고, 아버지 형제들과 할아버지는 1촌, 나와 아버지 형제들과는 3촌이 된다.

여러 사람들에 대한 부모 자식들 간의 관계가 주어졌을 때, 주어진 두 사람의 촌수를 계산하는 프로그램을 작성하시오.

 

🤖 입출력 예시

 

🧐 난이도/소요 시간

✅ 난이도: solved.ac 기준 S2

✅ 소요 시간: 예전에 풀었던 문제라 측정 X

✅ 권장 시간: 1시간

 

💡 풀이

1) 문제 유형 파악

'촌수'라는 개념 자체가 계속해서 타고 들어가는 거라 보자마자 DFS로 풀어야겠다는 생각을 했다.

 

하지만 내 경험상 보통 DFS로 풀 수 있는 문제는 BFS로도 풀 수 있고 웬만하면 그 반대도 가능하기 때문에 BFS로도 풀어봤다. 아래 구현 부분에 두 코드를 모두 정리해두었다.

 

2) 아이디어 흐름

① DFS 기본 틀 구상

Step. 1: DFS 함수 인자 정의

❎ 촌수 기록용 변수 선언?

이건 틀렸다기보다 굳이 이렇게 할 이유가 없다고 생각되는 부분이다.

 

처음에는 촌수를 기록하기 위한 전역변수를 따로 선언해줬는데 DFS 함수에 값만 잘 넘겨준다면 전역변수를 사용하지 않고도 문제가 해결될 것 같았다.

 

✅ DFS 함수의 입력 = 시작 노드, 촌수 초기값

전역변수를 사용하지 않기 위한 방법은 촌수 초기값을 DFS 함수의 인자로 넘겨주는 것이다.

 

현재 노드와 연결된 노드를 하나씩 확인하면서 방문하지 않은 노드일 경우 DFS 함수를 호출하게 되는데, 이 때 현재 촌수+1을 함께 넘겨주면 재귀가 깊어지면서 자연스럽게 촌수가 증가하게 된다.

 

Step. 2: 재귀 종료 조건 설정

✅ 현재 노드가 t2면 함수 종료

 

촌수를 계산해야 하는 서로 다른 두 사람의 번호를 target1, target2라는 의미에서 t1, t2로 지었기 때문에 '현재 노드가 t2면 함수 종료'라고 적었다.

 

Step.1에서 DFS 함수를 시작 노드와 촌수 초기값을 인자로 받는다고 했는데 이 때 시작 노드로 t1을 사용했다. 예제 입력 1을 이용해 t1에서 t2로 가는 과정은 아래 표와 같다.

 

현재 확인 중인 노드가 3이라면 더 탐색할 필요 없이 함수를 종료하면 된다.

 

Step. 3: answer 리턴 결과 확인

DFS 코드에서 주석으로 '이 부분 없으면 틀림'이라고 돼있는 두 줄을 넣는 게 제일 어려웠다. 이 부분의 작동 방식 이해를 위해 아래처럼 print문을 추가해 결과를 찍어봤다.

 

 

 

이게 글로 적으면 잘 전달될지 모르겠지만 일단 적어보자면..!

 

함수는 DFS(7, 0) → DFS(2, 1) → DFS(3, 3) 순서로 호출되고 DFS(3, 3)은 t2 == 3이기 때문에 현재까지 기록된 촌수 3을 리턴한다. 그럼 DFS(3, 3)으로부터 리턴된 값이 None이 아니기 때문에 answer 값 또한 3이 된다.

 

그리고 종료 조건이 호출된 상태로부터 다시 이전 함수로 돌아와 계속해서 값을 리턴해주는데 answer 값은 3으로 변화가 없고 None도 아니기 때문에 계속 3이 리턴되어 최종 값이 된다. → 이 부분 뭔가 설명이 이상해서 혹시나 이 글을 보고 계신 분이 있다면 일단 패스해주시기를,,⭐

 

② BFS 기본 틀 구상

BFS는 일반적으로 사용하는 그 구조대로 구현해주면 된다. 이 문제에서 신경 썼던 부분은 현재 노드와 촌수를 하나의 튜플로 묶어 큐에 같이 넣어준 것이다.

 

3-1) 구현: DFS

N = int(input())

t1, t2 = map(int, input().split())

M = int(input())

family = {k: [] for k in range(1, N+1)}

visited = [False]*(N+1)

for _ in range(M):
    x, y = map(int, input().split())    # x는 y의 부모
    
    family[x].append(y)
    family[y].append(x)

def DFS(node, score):    
    visited[node] = True
    
    if node == t2:
        return score
    
    for child in family[node]:
        if not visited[child]:
            answer = DFS(child, score+1)
            
            # 이 부분 없으면 틀림
            if answer is not None:
                return answer

answer = DFS(t1, 0)

if answer is None:
    print(-1)
else:
    print(answer)

 

3-2) 구현: BFS

N = int(input())

t1, t2 = map(int, input().split())

M = int(input())

family = {k: [] for k in range(1, N+1)}

visited = [False]*(N+1)

for _ in range(M):
    x, y = map(int, input().split())    # x는 y의 부모
    
    family[x].append(y)
    family[y].append(x)

def BFS(node, depth):
    from collections import deque
    
    queue = deque([(node, depth)])
    
    visited[node] = True
    
    while queue:
        current_node, current_depth = queue.popleft()

        if current_node == t2:
            return current_depth
        
        for member in family[current_node]:
            if not visited[member]:
                visited[member] = True
                queue.append((member, current_depth+1))
            
    return None

answer = BFS(t1, 0)

print(answer)

 

예전에 다른 문제 풀이에서 'BFS가 DFS보다 빠르다고 하지만 나는 아직까지 BFS가 더 빨랐던 문제를 본 적이 없다'고 쓴 적이 있다.

 

이 문제에서도 DFS의 실행 시간은 32ms, BFS의 실행 시간은 52ms로 DFS가 더 빠른 것을 확인할 수 있었다. 이유가 뭐지?

 

4) 어려웠던 점/배운 점

🚨 어려웠던 점

• DFS는 재귀를 쓰지만 내가 문제를 풀 때 재귀 개념을 완벽하게 이해했다기보다 코드를 하나의 템플릿처럼 외워두고 사용해서 그런가 어느 시점에서 결과 값을 return 해야 하는지 정하는 게 항상 어렵다.
• 이 부분은 재귀 공부를 추가적으로 해야만 해결될 것이기 때문에 시간 내서 재귀에 대해 다시 봐야겠다.

❗ 배운 점

• DFS 문제를 양치기 하는 것도 좋지만 난 그 전에 재귀 개념을 완벽하게 이해하는 것이 더 좋을 것 같다 ^^..