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

이번 문제는 거대한 2d array를 사용해 풀었다. 다만 해설지를 보았더니 내가 찾아낸 방법은 저장공간 사용량이 매우 클 수 있어 잘 쓰지는 않는 방법이었다. 

import numpy as np

# 노드정의
N, M, K = map(int, input().split())

# 선로정의
# connect = []
# for i in range(M):
# 	n, m = map(int, input().split())
# 	connect.append([n, m])
connect = np.zeros((N+1, N+1), dtype=int)
for i in range(M):
	n, m = map(int, input().split())
	connect[n][m] = 1
	connect[m][n] = 1

node_count = 1

while connect[K].sum() > 0:
	connect[:, K].fill(0)
	K = np.nonzero(connect[K])[0][0]
	node_count += 1
	# print(K)
	# print(connect)
	
print(node_count, K)

나는 가로세로 각각 N+1 크기의 2차원 배열을 만들었다. 그리고 그래프의 선로를 표시해 주기 위해 두 노드 사이에 선로가 있으면 1, 없으면 0으로 놔두었다. 그리고 while을 사용해 만약 현재 노드에서 갈 수 있는 선로가 하나도 없으면, 즉 sum() 값이 0이면 더 이상 탐색이 불가능하다고 보고 while의 조건으로 걸었다. 그리고 노드를 방문했으면 그 방문한 노드로 향하는 선로는 0으로 만들어줌으로써 노드를 한 번만 방문할 수 있게 만들었다. 

 

이번에는 상당히 간단히 풀리는 방법이고 코드 실행시간도 아주 길지는 않아서 내가 맞는 방법을 찾았나 생각했지만 내가 찾은 방법보다 더 좋은 방법이 있었다. Adjacency List를 사용하는 방법으로서 공간복잡도 측면에서 훨씬 효율적이다. 

N, M, K = map(int, input().split())

# 인접 리스트 방식으로 그래프를 만듭니다.
graph = [[] for _ in range(N + 1)]

for _ in range(M):
	s, e = map(int, input().split())
	graph[s].append(e)
	graph[e].append(s)

이렇게 list를 만들어 인접한 노드를 리스트에 저장해 주면 딱 선로정보만 저장해 줄 수 있다.

# 0 이면 아직 방문하지 않은 것이고, 1 이면 이미 방문한 것입니다.
visited = [0] * (N + 1)

# BFS 함수를 선언합니다.
def bfs(start):
	# 큐 선언 대신에 현재 노드를 선언해줍니다.
	now = start

	# return 되기 전까지 반복합니다.
	while True:
		# 현재 노드를 방문처리합니다.
		visited[now] = 1
		
		for to in sorted(graph[now]):
			# now를 갱신하고 break 합니다.
			if not visited[to]:
				now = to
				break
		else:
			return now

그래프 탐색은 방문한 노드를 표시해 주는 리스트를 하나 만들고 위의 코드처럼 탐색하면 된다. 

 

내 방법이 아주 틀린 것은 아니지만 효율적인 코드에 대해서 좀 더 생각해 보아야겠다. 그리고 break를 사용하지 말라고 배워서 그런지 break를 사용하는데 익숙지가 않다. break사용에도 좀 더 익숙해져야겠다.