[구름톤 챌린지] Day19 : 대체 경로

입력 및 출력

소스 코드

n, m, start, end = map(int, input().split())
graph = [[] for _ in range(n+1)]
for _ in range(m):
	a, b = map(int, input().split())
	graph[a].append(b)
	graph[b].append(a)
for i in range(1, n+1):
	if i == start or i == end:
		print(-1)
		continue
	visited = [False for _ in range(n+1)]
	q = [start]
	visited[start] = True
	depth = 1
	ended = False
	while len(q) != 0 and not ended:
		nextq = []
		for now in q:
			if now == end:
				print(depth)
				ended = True
				break
			for nextNode in graph[now]:
				if nextNode == i:
					continue
				if not visited[nextNode]:
					nextq.append(nextNode)
					visited[nextNode] = True
		q = nextq
		depth += 1
		if len(q) == 0 and not visited[end]:
			print(-1)
			break

문제 풀이

문제에서는 i일마다 i번째 도시에 공사를 한다. 이런식으로 설명이 되어있지만, 실제로 문제의 답을 구하는 건 i번째 도시가 공사중일 경우 최단 경로를 각각 케이스마다 구하면 된다. 요구하는 것을 잘 파악해야 하는 문제이다.

0. 그래프 구축

1. for문으로 공사중인 도시를 하나씩 바꿔가면서 탐색한다.

2. collections 라이브러리에서 deque를 가져와서 BFS를 하지 않고, depth 기준으로 탐색을 하기 위해서 리스트 2개로 너비 우선 탐색을 했다.

3. 탐색을 종료하는 조건은 (1) 도착해야하는 노드에 도착했거나 (2) 모든 탐색을 종료했거나 이다.

4. 탐색이 종료됐을 때 도착하는 노드에 도착해서 끝났을 경우와 공사중인 노드로 인해 도착점 노드에 도착하지 못했음에도 탐색이 끝났을 경우가 있다. → 그래서 맨 밑에 len(q) == 0 and not visited[end] 조건을 통해 어떤 경우로 탐색이 종료됐는지 판단하고 종료한다.

느낀 점

bfs의 특성상 함수로 만들지 않아도 코드 블럭에서 작성할 수 있다. 그래서 반복문 안에서 직접 구현하고 조건에 따라 종료하려고 코드를 짜다보니, ended와 같은 변수들을 사용하게 되었다. 다 작성하고 코드를 보니까 가독성이 상당히 떨어지는 것 같은 느낌이 든다.

앞으로는 그냥 함수 만들어서 써야겠다. 특히나 파이썬은 전역변수, 함수의 인자들이 아주 말을 잘 듣기 때문에(C 언어로 포인터 썼던 기억을 되살려보면 얼마나 친절한지 깨달을 수 있다.) 앞으로는 함수로 만들어보겠다.