[구름톤 챌린지] Day 14 - 작은 노드(그래프)

https://level.goorm.io/exam/195696/%EC%9E%91%EC%9D%80-%EB%85%B8%EB%93%9C/quiz/1

구름LEVEL

---

문제

---

풀이

n,m,k = map(int,input().split())

graph = [[]*(n+1) for _ in range(n+1)]
for _ in range(m):
	a,b = map(int,input().split())
	graph[a].append(b)
	graph[b].append(a)


cnt = 1
visited = [0]*(n+1)

num = []
num.append(k) # 왔다갔다할 리스트
visited[k] = 1 # 방문처리

while num:
	now = num[0]
	num.pop() # 현재 노드 pop
	if graph[now]: # 다음 노드가 있을때
		graph[now].sort() 
		for i in range(len(graph[now])): # 최소값 노드 만들기
			if visited[graph[now][i]] != 1: # 간적 없고 자신보다 낮지않을때
				visited[graph[now][i]] = 1 # 갈거니까 방문처리
				cnt +=1
				num.append(graph[now][i])
				break
			else:
				pass


print(cnt,now)

1. graph를 만드는법 : [ []*(n+1) for _ in range(n+1)]을 사용해서 빈 리스트를 만들어주고 연결된 노드마다 a,b를 각각 인덱스에 넣어줌. 예를들어 1번과 2번이 연결됐을 경우, 이중리스트의 1번 인덱스에 2번 노드 넣고 2번인덱스에 1번노드를 넣어서 서로 연결됐음을 알려줌

2. 이후 다음 노드가 있는지 없는지 확인하고 최소값노드를 sort로 구분

3. 간적 없고 자신보다 낮지않을때 방문하면서 갯수 세기