[구름톤 챌린지 #14] 작은 노드

문제14. 작은 노드

구름LEVEL

---

---

문제 해결 방법

오늘의 문제는 자료구조 중 하나인 그래프에 대한 기본적인 지식을 알고 있다면 어렵지 않은 문제이다.

 

그래프는 크게 두 가지 방법으로 표현할 수 있다. 바로 이차원 배열을 사용하는 방식인 인접행렬 방식과, 연결리스트를 사용하는 방식인 인접리스트 방식이다. 두 표현 방법 중 탐색에서 더 큰 효율을 보여주는 방법은 인접행렬 방식이다(단, 메모리 공간을 많이 소모한다는 단점이 있다.). 

 

그래서 이 문제에서 내가 택한 방식은 인접행렬 방식이다. 인접행렬 방식은 이차원 배열의 각 인덱스가 노드가 되고,  두 인덱스로 접근한 배열의 값이 1이면 두 노드 사이에 간선이 있음을 나타낸다. 문제를 풀 때 주의깊게 봐야하는 부분은 아래와 같다.

• 간선은 양방향 간선이다. 따라서 배열에 값을 저장할 때, node1 -> node2 로 가는 간선과 node2 -> node1 로 가는 간선을 모두 입력해줘야한다.
• 한번 방문한 노드는 방문할 수 없다. 따라서 이미 방문한 노드인지를 확인할 수 있도록 visited Set에 방문한 노드를 넣어주고, 탐색시에 Set을 확인하여 이미 방문한 노드인지를 체크해주어야한다.
• 방문할 수 있는 노드 중 가장 작은 노드로 이동한다. 따라서 다음 노드로 이동할 때, 각 노드를 작은 숫자부터 순차적으로 체크하면서 다음 이동할 노드를 결정해야한다.

위 내용들을 고려하고 문제를 푼다면, 어렵지 않게 문제를 해결할 수 있다.

 

위 내용을 코드로 구현하면 아래와 같다.

import sys

n, m, k = map(int, sys.stdin.readline().split())

arr = [[0 for i in range(n + 1)] for j in range(n + 1)]

for i in range(m):
    node1, node2 = map(int, sys.stdin.readline().split())
    arr[node1][node2] = 1
    arr[node2][node1] = 1

visited = set()
visited.add(k)

count = 1
while True:
    for j in range(1, n + 1):
        if arr[k][j] == 1:
            if j not in visited:
                visited.add(j)
                count += 1

                k = j
                break
    else:
        break

print(count, k)