[ 구름톤 챌린지 ] 14일차 미션 - 작은 노드

구름톤 챌린지 14일차입니다. 챌린지를 통해 문제 풀이 실력을 향상시킬 수 있으며, 블로그에 학습 일기도 작성하면 추가 보상도 주어지니 관심 있으시면 참여해보시는 것을 추천드립니다.

https://level.goorm.io/l/challenge/goormthon-challenge

구름LEVEL

 

문제

입력 / 출력

풀이 과정

그래프 이론에 대해 다루는 문제이다. 간선 정보를 등록하여 탐색을 이어나가면 결과를 쉽게 구할 수 있다.

import sys
input = sys.stdin.readline

n, m, k = map(int, input().rstrip().split())
graph = [[] for _ in range(n+1)]
for _ in range(m):
	s, e = map(int, input().rstrip().split())
	graph[s].append(e)
	graph[e].append(s)

visited = [0 for _ in range(n+1)]
visited[k] = 1

now = k
cnt = 1

while True:
	available = []
	for i in graph[now]:
		if visited[i] == 0:
			available.append(i)
	
	if len(available) == 0: break
	now = min(available)
	cnt += 1
	visited[now] = 1

print(cnt, now)

혹은 우선순위 큐를 이용하여 구현할 수 있다.

import sys
import heapq
input = sys.stdin.readline

n, m, k = map(int, input().rstrip().split())
graph = [[] for _ in range(n+1)]
for _ in range(m):
	s, e = map(int, input().rstrip().split())
	heapq.heappush(graph[s], e)
	heapq.heappush(graph[e], s)

visited = [0 for _ in range(n+1)]
visited[k] = 1

now = k
cnt = 1

while True:
	while len(graph[now]) != 0:
		if visited[graph[now][0]] == 1:
			heapq.heappop(graph[now])
		else:
			break
	
	if len(graph[now]) == 0: break
	now = graph[now][0]
	cnt += 1
	visited[now] = 1

print(cnt, now)