[멀티잇 코딩테스트 러닝클래스] 그래프(Graph) : 구름이의 여행 - 파이썬(Python)

구름이의 여행

 

 

 

 

 

 

 

---

 

기본적인 그래프 탐색 문제입니다.

먼저 노드들이 서로 어떻게 연결되어있는지 파악하기 위해서 그래프를 만들어봅니다.

defaultdict를 호출하여 그래프를 선언하고, 반복문을 통해 start와 end가 서로 이어지도록 그래프에 추가했습니다.

 

 

from collections import defaultdict

graph = defaultdict(list)
for i in range(M) :
	start,end = map(int,input().split())
	graph[start].append(end)
	graph[end].append(start)

 

 

다음으로 현재 노드들이 담길 Q(양방향 큐)와 노드별 최소 경로를 저장하는 배열 Visited를 저장합니다. Visited를 선언할 때는 최댓값들을 원소로 지정해주면 좋습니다. 

 

문제를 보면 항상 1번 노드부터 시작하기 때문에, Q에 1을 미리 추가하고 Visited[1] 에 0을 저장 (1번 노드에서 1번 노드로 이동하는 거리는 0)했습니다.

 

 

from collections import deque
	
Q = deque()
Q.append(1)

Visited = [10e9 for _ in range(N+1)]
Visited[1] = 0

 

 

이제 그래프를 탐색하며 Visited에 노드별 최소 경로를 저장해보겠습니다.

Q의 첫 번째 원소를 cur_node / graph[cur_node]에 속해있는 원소들을 next_node라 할 때,

Visited[next_node] = Visited[cur_node] + 1 (서로 한 칸 떨어져있음)로 작성해 볼 수 있습니다.

하지만 Visited[next_node]에 이미 Visited[cur_node] + 1보다 작거나 같은 수가 들어가 있다면 그 수가 바로 지금까지의 최소 경로이기 때문에 최신화시킬 필요가 없습니다.

 

 

while Q :
	cur = Q.popleft()
	for next in graph[cur] :
		if Visited[next] <= Visited[cur] + 1 :
			continue
		Visited[next] = Visited[cur] + 1
		Q.append(next)

 

 

Q가 비어있을 때까지 Visited에 최소 경로 저장이 끝났다면, 이제 1번 노드부터 N번 노드까지의 최소 경로 즉, Visited[N]이 K보다 작거나 같은지 확인합니다. 만약 K보다 작거나 같다면 "YES"를, 그렇지 않다면 "NO"를 출력하면 됩니다.

 

최종 코드는 아래와 같습니다.

 

 

from collections import defaultdict,deque
import sys
input = sys.stdin.readline
N,M,K = map(int,input().split())

graph = defaultdict(list)
for i in range(M) :
	start,end = map(int,input().split())
	graph[start].append(end)
	graph[end].append(start)
	
Q = deque()
Q.append(1)

Visited = [10e9 for _ in range(N+1)]
Visited[1] = 0
while Q :
	cur = Q.popleft()
	for next in graph[cur] :
		if Visited[next] <= Visited[cur] + 1 :
			continue
		Visited[next] = Visited[cur] + 1
		Q.append(next)
	
if Visited[N] <= K :
	print("YES")
else :
	print("NO")