[PS] 3/2 - BOJ 2644 촌수계산 - DFS

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

2644번: 촌수계산

 

나는 촌수계산하려면 각각 노드 간 깊이를 계산해줘야 되니까 DFS가 먼저 떠올랐는데 다른 사람들은 BFS로 풀었다고 한다.

왜 BFS라고 생각을 했을까?

 

출처 https://velog.io/@tyjk8997/백준-BFS-촌수계산python

 

DFS랑 풀이법은 비슷한데 큐에 튜플을 통해서 (시작노드, cnt)를 넣어준 것이 BFS 특징

이렇게도 풀 수 있다는 걸 익혀야겠다. 

 

 

우선, 하나씩 x = 7인 경우부터 노트에 다 그려보면서 이해를 했다.

depth의 경우, 7 시작노드와 연결된 노드들 (여기서는 2)에게 +1씩 해준다.

7-2 : 1

재귀적으로 dfs(2)가 호출돼서 시작노드 2를 기준으로 인접한 노드들 (여기서는 1, 7, 8, 9)를 탐색하면서 +1씩 해준다.

2-1 : 1

2-7 : 이미 방문했으니까 패스

2-8 : 1

2-9 : 1

 

그러면 결론적으로 나는 7-2-1 / 7-2-8 / 7-2-9 간의 촌수가 2라는 것을 알 수 있다.

글구, 전역변수 total을 통해 구한 depth 값을 대입한 후에 total을 출력하면 된다.

 

여기서 내가 막힌 부분이 촌수 간 연결되지 않은 경우 -1을 반환하는 건데, 이건 찬마의 힌트를 통해 해결했다.

나는 초반에 total을 지역변수로 설정했는데 전역변수로 고치고 해결했다. 지역변수로 설정할 경우에, x != b인 경우가 항상 있어버리니까 문제가 됐다. 전역변수로 해주면 기본적으로 dfs를 돌면서 인접노드, 연결노드가 아니면 반환할 값이 없기 때문에 항상 total이 -1은 변하지 않아서 -1을 출력하게 된다.

 

https://github.com/heerucan/PS/commit/97b6952dbc3b02c52b436122f874dd55a64ad388