[백준/python] 2644 - 촌수계산

2644번: 촌수계산

all_people = int(input())
target_a, target_b = map(int, input().split())
m = int(input())

graph = [[] for _ in range(all_people + 1)]
visited = [False] * (all_people + 1)

for _ in range(m):
    x, y = map(int, input().split())
    graph[x].append(y)
    graph[y].append(x)

def dfs(v, cnt):
    visited[v] = True
    cnt += 1
    if v == target_b:
        visited[v] = cnt

    for i in graph[v]:
        if visited[i] == False:
            dfs(i, cnt)

dfs(target_a, 0)

target = visited[target_b]
if target == True or False:
    print(-1)
else:
    print(target - 1)

| 풀이

dfs로 풀이. dfs에 처음 target_a를 넣고,  깊이가 깊어질 때 마다 cnt를 +1 해준다. v가 target_b일 때만 계산한 cnt를 visited에 넣어준다. 다 탐색이 끝나면 target을 검사하여 숫자를 갖고 있으면 값에 -1 하여 출력한다.

| 알게된 점 

일단 오랜만에 dfs라 상당히 고민하면서 풀었다. 다시 한번 재귀함수를 이용한 dfs에 대해서 탐구해보는 시간. 우선

all_people = int(input())
target_a, target_b = map(int, input().split())
m = int(input())

graph = [[] for _ in range(all_people + 1)]
visited = [False] * (all_people + 1)

for _ in range(m):
    x, y = map(int, input().split())
    graph[x].append(y)
    graph[y].append(x)

def dfs(v, cnt):
    visited[v] = v
    cnt += 1
    print(visited, cnt)
    if v == target_b:
        visited[v] = cnt

    for i in graph[v]:
        if visited[i] == False:
            print(visited, cnt)
            dfs(i, cnt)

dfs(target_a, 0)

target = visited[target_b]
if target == True or False:
    print(-1)
else:
    print(target - 1)

로 print와 visited[v] = v로 바꾸면

[False, False, False, False, False, False, False, 7, False, False] 1
[False, False, False, False, False, False, False, 7, False, False] 1
[False, False, 2, False, False, False, False, 7, False, False] 2
[False, False, 2, False, False, False, False, 7, False, False] 2
[False, 1, 2, False, False, False, False, 7, False, False] 3
[False, 1, 2, False, False, False, False, 7, False, False] 3
[False, 1, 2, 3, False, False, False, 7, False, False] 4
[False, 1, 2, 4, False, False, False, 7, False, False] 2
[False, 1, 2, 4, False, False, False, 7, 8, False] 3
[False, 1, 2, 4, False, False, False, 7, 8, False] 2
[False, 1, 2, 4, False, False, False, 7, 8, 9] 3

이러한 출력 결과가 나온다. 깊어질수록 cnt를 +1하고 target_b와 v가 같을 시 visited를 갱신하기 때문에 최종 -1을 하고 출력을 한다. 재귀의 개념이 아직 정립되지 않아서 함수의 함수로 들어가는 구조를 이번 기회에 잘 알게됨.

for문을 다 돌고, if문에 걸리지 않으면 그 함수는 끝나게 되고, 위의 함수로 돌아오기 때문에 기존의 cnt값은 돌아온다. 통안의 통인 셈. 즉, 재귀 함수에 cnt라는 변수를 넣는 순간 다른 변수로 재선언 되는 것과 마찬가지이다.

또한 dfs를 풀 때, 방향이 있지 않으면 x와 y를 각각 다 넣어주고, dfs를 시작할 때, 굳이 for문으로 처음부터 돌리지 않고 이번 문제와 같이 처음부터 목표를 dfs에 처음에 넣고 실행할 수도 있다는 것을 알게되었다.