https://level.goorm.io/exam/195696/작은-노드/quiz/1
예시 데이터
1
2
3
4
5
6
7
| n, m, k = 6, 6, 1
nodes = [[1, 2],
[1, 3],
[2, 3],
[3, 4],
[3, 5],
[4, 6]]
|
그래프 생성
1
2
3
4
5
| graph = [[] for _ in range(n+1)]
for node in nodes:
s, e = node
graph[s].append(e)
graph[e].append(s)
|
1
2
| graph
> [[], [2, 3], [1, 3], [1, 2, 4, 5], [3, 6], [3], [4]]
|
그래프 정렬
낮은 것 부터 찾기 위해서
1
2
| for i in range(1, n+1):
graph[i].sort()
|
1
2
| graph
> [[], [2, 3], [1, 3], [1, 2, 4, 5], [3, 6], [3], [4]]
|
하나씩 방문
1
2
3
4
5
6
7
8
9
10
11
12
13
| visited = [False] * (n+1)
cnt = 1
current_node = k
while True:
visited[current_node] = True
for next_node in graph[current_node]:
if not visited[next_node]:
current_node = next_node
cnt += 1
break
else:
break
|
for else를 사용해서, 그래프의 모든 곳을 방문한 후에 else 구분으로 이동한다. ➡️ while 문 탈출
출력
1
2
| cnt, current_node
> (5, 6)
|