Problem

가중치가 없는 무향 그래프를 다음 조건에 따라 탐색하여 (방문한 노드의 개수, 마지막 방문 노드)를 출력한다.

1. 한 번 방문한 노드는 다시 방문할 수 없다.
2. 방문할 수 있는 노드가 여러 개일 때, 번호가 가장 작은 노드로 이동한다.

Submitted Code

Python

 1 N, M, K = map(int, input().split())
 2 graph = {i: [] for i in range(1, N + 1)}
 3 for _ in range(M):
 4     node1, node2 = map(int, input().split())
 5     graph[node1].append(node2)
 6     graph[node2].append(node1)
 7
 8 for i in range(1, N + 1):
 9     graph[i].sort(reverse=True)
10
11 visited = [0] * (N + 1)
12 visited[K] = 1
13 while len(graph[K]):
14     node = graph[K].pop()
15     if visited[node]:
16         continue
17     K = node
18     visited[K] = 1
19	
20 print(sum(visited), K)

Line 1

입력으로 주어진 N, M, K을 받아온다.

Line 2-6

입력으로 주어진 에지 리스트를 딕셔너리를 활용한 인접 리스트로 받아온다.

• 에지 리스트 : 각 에지(간선)에 대해 출발 노드와 도착 노드의 쌍으로 표현한 그래프
• 인접 리스트 : 각 출발 노드에 대해 연결된 도착 노드들을 리스트로 묶어 표현한 그래프

방향이 정해지지 않았기 때문에 node1 → node2 방향과 node2 → node1 방향으로 모두 이동할 수 있다.

Line 8-9

문제에 주어진 조건 2에 의해 번호가 작은 순으로 도착 노드를 선택할 수 있도록 정렬한다.

• 도착 노드 리스트를 stack으로 사용하기 위해 내림차순으로 정렬했다.
  • stack.pop()으로 마지막 요소부터 사용하고자 한다.
• 새로운 리스트를 반환하지 않고 기존 리스트를 수정하는 graph[i].sort() 대신 새로운 리스트를 반환하는 sorted(graph[i])를 사용할 수 있다.
  • 하지만, 기존 리스트를 보관할 필요가 없었기 때문에 새로운 리스트를 반환하는 경우는 메모리 낭비라고 생각했다.

Line 11-12

방문한 노드를 기록할 visited 리스트를 0으로 초기화하고, 출발 노드인 K의 방문을 업데이트했다.

• visited 리스트를 False로 초기화할 수도 있다.
  • 하지만, 이후 방문한 노드의 개수를 sum(visited)로 출력하기 위해 int 자료형을 선택했다.

Line 13-18

출발 노드 K에서 이동할 수 있는 도착 노드가 존재하지 않을 때까지 while 문 내부 코드를 반복 실행한다.

Line 14

도착 노드 리스트에서 마지막 요소를 제거하고 해당 요소를 node에 대입한다.

Line 15-16

node가 이미 방문한 노드라면, 이후 코드를 진행하지 않고 while문을 다시 실행한다.

Line 17-18

node가 처음 방문하는 노드라면, K를 node로 업데이트하고 visited에 방문했음을 기록한다.

Line 20

더이상 방문할 수 있는 노드가 없어 while문이 종료되면, visited의 합을 계산하여 방문 노드의 개수를 구한다. 방문 노드의 개수와 마지막 방문 노드 K를 함께 출력한다.

• print 함수에서 comma(,)로 구분해 입력하면 공백으로 두 값을 연결하여 출력하기 때문에, 별도의 공백을 입력하지 않아도 된다.