[구름톤 챌린지] 4주차 문제 19. 대체 경로

이번에도 문제를 찬찬히 풀어보지는 못하고 내가 약한 그래프와 BFS관련된 문제를 찬찬히 들여다보게 되었다. 

 

일단 입력값을 받아 그래프를 만들어주는 과정부터 필요하다. 

N, M, S, E = map(int, input().split())
graph = [[] for _ in range(N + 1)]

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

graph = [[] for _ in range(N + 1)]을 보면 이번에도 list comprehension 이 사용되었다. list 내에 list를 만들어줌으로써 list의 index를 각 도시번호로 사용하고, 각 도시가 어느 도시에 연결되어 있는지 저장할 수 있게 만든 것 같다. 

 

그리고 밑의 for 문은 input을 받음으로써 각 도시가 어느 도시에 연결되어 있는지 graph list내의 list에 저장해 준다. 다만 양방향 도로이므로 저렇게 처리해 준 것 같다. 

 

그리고 bfs로 답을 출력해 주는 코드를 작성했다.

for i in range(1, N + 1):
	print(bfs(S, i))

여기서 BFS란 Breadth First Search라고 너비 우선 탐색 방법이라고 한다. 시작 노드에서 인접한 노드를 먼저 방문하고 멀리 떨어져 있는 노드는 나중에 방문하는 방식이라고 한다. 알고리즘 강의 시간에 배웠던 것 같은데 가물가물 하다. 그리고 queue를 사용하며  FIFO원칙으로 탐색한다고 한다. 

아마 그래프 탐색 문제 중 하나라 BFS방법이 나온 것 같다. 

 

이제 bfs코드를 작성해 주면 된다. 

from collections import deque

def bfs(start, off):
	if start == off:
		return -1

queue를 사용하기 위해 deque를 import 해주고 만약 시작점과 공사 중인 도시가 같다면 바로 -1을 리턴해준다.

 

visited = [0] * (N + 1)
	q = deque([start])
	
	visited[start] = 1

	step = 1

각 도시를 방문했는지 체크하기 위해 list를 생성해 주고 아무 데도 방문하지 않았으므로 [0]으로 initialize 한다. 그리고 deque를 선언해 준다. deque선언할 때 시작하는 도시를 deque([시작도시])로 넣어주면 큐 안에는 도시 한 개만 저장되어 있다. 

그리고 visited[시작도시] = 1로 방문체크를 해준다. 그리고 최단경로를 세기 위한 변수인 step=1도 선언해 준다. 시작점도 포함이라 =1로 선언해 주었다.

	while q:		
		step += 1
		for _ in range(len(q)):
			now = q.popleft()

while q: 이렇게 쓴 이유는 deque는 만약 que 가 비어있으면 False를 return 하기 때문에 deque에 element가 들어가 있는 이상 True가 리턴되어 계속 알고리즘을 실행하기 위해 저렇게 쓴 것 같다. 일단 다음 도시로 이동하는 것은 확정이니 step+=1을 해준다. 그리고 for 문으로 deque안에 element가 몇 개 들어있던 element를 다 탐색할 수 있게 for문을 사용한 것 같다. 그리고 q.popleft()을 이용해 deque안에 있는 도시중 하나를 방문한다고 가정한다. 

			for to in graph[now]:
				if visited[to] or to == off:
					continue

그리고 현재 도시에서 방문할 수 있는 모든 도시를 탐색하는데, 만약 방문할 수 있는 도시가 이미 방문했던 도시거나, 공사 중인 도시인 경우에는 continue로 건너뛰어준다. 

				if to == E:
					return step

만약 현재 도시에서 방문할 수 있는 도시들 중 하나가 최종 도착 도시이면 최단 경로를 통해 도달한 것이므로 방문한 도시들을 센 함수인 step를 반환해 주면 된다.

				visited[to] = 1
				q.append(to)

만약 현재 도시에서 방문할 수 있는 도시가 위의 두 가지 경우에 포함되지 않는다면 방문체크를 하고 deque에 추가해 주어 다음에 탐색할 수 있게 하면 된다.

 

return -1

하지만 위의 코드들이 정상적으로 실행되었다면 최종 방문도시를 탐색하면서 마주쳤기 때문에 bfs함수가 종료되었겠지만 그렇지 않고  deque가 빌 때까지 최종 방문도시에 도착히지 못했다면 최종 방문도시에 도착하는 것이 불가능하다는 뜻이기 때문에 -1을 반환해 주고 bfs함수를 종료시켜 준다. 

 

 

이번 해설지를 찬찬히 들여다보면서 deque를 그래프 문제에서 어떻게 사용하는지 알아볼 수 있었다. 그리고 bfs를 어떻게 문제를 해결하기 위해 구현하는지 좀 더 자세히 볼 수 있었다. 다만 for 문에서 continue를 사용해 본 적이 없어  continue는 좀 사용해 보아야겠다.

 

from collections import deque

def bfs(start, off):
	if start == off:
		return -1
	
	visited = [0] * (N + 1)
	q = deque([start])
	visited[start] = 1
	step = 1
	
	while q:
		step += 1
		for _ in range(len(q)):
			now = q.popleft()

			for to in graph[now]:
				if visited[to] or to == off:
					continue
					
				if to == E:
					return step
				
				visited[to] = 1
				q.append(to)
	
	return -1
	
N, M, S, E = map(int, input().split())
graph = [[] for _ in range(N + 1)]

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

for i in range(1, N + 1):
	print(bfs(S, i))