[구름톤 챌린지] 3주차 14일차 작은 노드

 

 

문제

---

$N$개의 노드와 $M$개의 양방향 간선으로 이루어진 그래프가 있다. 이 그래프의 노드는 $1$번부터 $N$번까지 번호가 붙어 있다. 양끝 노드가 동일한 간선은 주어지지 않는다.

플레이어는 아래 규칙에 따라 그래프에서 이동하려고 한다. 플레이어는 처음에 $K$번 노드에 있다.

 

 

• 한 번 방문한 노드는 다시 방문할 수 없다. 시작 노드도 방문한 것으로 간주한다.
• 현재 노드와 간선으로 직접 연결된 다른 노드 중, 방문할 수 있으면서 번호가 가장 작은 노드로 이동한다.

플레이어가 더 이상 이동할 수 있는 노드가 없을 때, 방문한 서로 다른 노드의 개수와 마지막 노드 번호를 구해보자.

입력

---

첫째 줄에 노드의 개수 $N$, 간선의 개수 $M$, 시작 노드의 번호 $K$가 공백을 두고 주어진다.
다음 $M$개의 줄에는 간선이 잇는 양끝 정점의 번호 $s_i, e_i$가 공백을 두고 주어진다.

 

• $1 \leq N \leq 2 \ 000$
• $1 \leq M \leq 200 \ 000$
• $1 \leq K \leq N$
• $1 \leq s_i, e_i \leq N ; s_i \neq e_i$

출력

---

플레이어가 더 이상 이동할 수 없을 때까지 방문한 노드의 개수와 마지막 노드의 번호를 출력한다.

 

---

문제 접근 방식

---

기본적인 접근 방식은 DFS를 변형한 접근이었다.

 

먼저, 문제에서 주어진 그대로 입력을 받았다.

 

이후, 그래프를 각 노드 별로 정렬해주었다.

 

현재 노드를 $K$라고 할 때, 문제에서 주어진 조건대로 계속 현재 노드를 갱신하며 탐색했다.

 

for문으로 탐색하면 가장 작은 번호 먼저 탐색을 하는데, 이때 아직 탐색하지 않은 노드가 있으면 갱신해주는 방식이다.

 

갱신함과 동시에 지금까지 탐색을 진행했던 개수 또한 카운팅 해주었다.

 

---

정답 코드

---

# 작은 노드
import sys
input = sys.stdin.readline

N, M, K = map(int, input().rstrip().split())
graph = [[] for _ in range(N+1)]
visited = [0 for _ in range(N+1)]
for _ in range(M):
    u, v = map(int, input().rstrip().split())
    graph[u].append(v)
    graph[v].append(u)
for i in range(N+1):
    graph[i].sort()
visited[K] = 1
stack = []
stack.append(K)
count = 1
while stack:
    K = stack.pop()
    for near_node in graph[K]:
        if visited[near_node] == 0:
            visited[near_node] = 1
            stack.append(near_node)
            count += 1
            break
print(count, K)

 

---

특별히 배운 점

---

다시 되돌아보니 굳이 스택을 안써도 while문과 변수 하나로만 충분히 탐색 가능한 문제였다.

 

DFS와 BFS의 틀에만 얽매이지 말아야 겠다는 생각을 했다.