[Algorithm] 백준 2644 - 촌수계산 in Python(파이썬)

💡 백준 2644:

DFS 탐색

🌱 코드 in Python

알고리즘: bFS

import sys

input = sys.stdin.readline

n = int(input())
c1, c2 = map(int, input().split())
t = int(input())
visit = [0] * (n + 1)
 
g = [[] for _ in range(n + 1)]
for _ in range(t):
	p, c = map(int, input().split())
	g[p].append(c)
	g[c].append(p)

q = []
q.append((c1, 0))

def bfs():
	while q:
		w, r = q.pop(0) # 다음 탐색 노드 및 그 노드와의 거리 계산 변수
		visit[w] = 1 
		for i in g[w]:
			if i == c2: # c2를 찾을 경우 그 때의 거리 반환하여 출력
				return (r + 1)
			if not visit[i]: # c2를 못찾았을 경우 방문하지 않은 노드 탐색 추가
				q.append((i, r + 1))
	return (-1) # c1에서 이어진 모든 노드들을 순회했음에도 불구하고 값을 찾지 못한 경우 -1 반환

print(bfs())

이번 문제는 촌수계산 문제로 자식이 여러 부모에 연결되지 않았다는 점에서
조금 더 직관적인 형태의 그래프 탐색 문제였다고 생각한다

나는 BFS 방식을 통해 해당 부모와 연결되어있는 자식을 모두 찾고 가는 형태였다

처음에는 사실 재귀문으로 풀고 싶었는데 찾았을 때 재귀 종료를 하는 방법을 몰라 선회했다.
BFS로 풀고나서 찾아보니, visit 배열을 -1로 초기화 후 거리 배열로 활용하는 dfs 풀이 방법이 있었다

알고리즘: DFS

import sys

input = sys.stdin.readline

n = int(input())
c1, c2 = map(int, input().split())
t = int(input())
d = [-1] * (n + 1)

g = [[] for _ in range(n + 1)]
for _ in range(t):
	p, c = map(int, input().split())
	g[p].append(c)
	g[c].append(p)

def dfs(g, w):
	for i in g[w]:
		if i == c2: # c2값을 찾았을 경우 더이상 거리 탐색을 하지 않을 수 있도록 조건문 추가
			d[i] = d[w] + 1 # 나의 전 단계까지 오기까지의 거리에 전 단계에서 나에게 오기까지의 거리 1 추가
		if d[i] == -1: # 찾고자 하는 값이 아닐 경우 dfs 계속 진행
			d[i] = d[w] + 1
			dfs(g, i)

d[c1] = 0 # 시작 지점만 거리 0으로 설정
dfs(g, c1)
print(d[c2])

어차피 시작 지점에서부터 어떤 한 정점을 방문할 때까지 도달하는 거리는 정해져있으므로
방문 배열을 거리 배열로 놓고 생각해도 풀이가 가능한 문제였다
또한 거리 배열을 -1로 초기화 해두면 마지막 종료 시점에 시작 지점에서 연결되지 않은 노드라면
자연히 -1을 뱉을 것이고, 아니라면 해당 거리를 출력하게 되어 있어 좋은 코드였다고 생각한다

🧠 기억하자

1. DFS & BFS 어려엉 ㅠ

백준 2644 바로가기