[ 구름톤 챌린지 ] 19일차 미션 - 대체 경로

구름톤 챌린지 19일차입니다. 구름톤 챌린지 종료까지 얼마 남지 않았습니다. 챌린지를 통해 문제 풀이 실력을 향상시킬 수 있으며, 블로그에 학습 일기도 작성하면 추가 보상도 주어지니 관심 있으시면 참여해보시는 것을 추천드립니다.

https://level.goorm.io/l/challenge/goormthon-challenge

구름LEVEL

 

문제

입력 / 출력

풀이 과정

특정 도시가 공사 중일 때를 고려하여 그래프 탐색을 진행하면 해결 가능한 문제이다.

BFS 를 사용하여 최단거리를 얻는 풀이이다.

import sys
from collections import deque
input = sys.stdin.readline

n, m, s, e = map(int, input().rstrip().split())
graph = [{} for _ in range(n+1)]
for _ in range(m):
	u, v = map(int, input().rstrip().split())
	graph[u][v] = 1
	graph[v][u] = 1

def bfs(cant_use):
	global graph
	global s
	global e
	global n
	
	queue = deque()
	queue.append(s)
	
	visited = [0 for _ in range(n+1)]
	visited[s] = 1
	
	done = 0
	cnt = 1
	while queue:
		len_queue = len(queue)
		for _ in range(len_queue):
			now = queue.popleft()
			if now == cant_use: continue

			for go in graph[now].keys():
				if visited[go] == 0 and go != cant_use:
					visited[go] = 1
					queue.append(go)

					if go == e:
						done = 1
						break
			if done == 1: break
		
		cnt += 1
		if done == 1: break
	
	if done == 1: return cnt
	else: return -1
	
for i in range(1, n+1):
	# i : 공사중인 도시
	print(bfs(i))

가중치가 1인 그래프로 설정하고 다익스트라 알고리즘을 사용하여 최단거리를 얻는 풀이이다.

import sys
import heapq
input = sys.stdin.readline

n, m, s, e = map(int, input().rstrip().split())
graph = [{} for _ in range(n+1)]
for _ in range(m):
	u, v = map(int, input().rstrip().split())
	graph[u][v] = 1
	graph[v][u] = 1

def dijkstra(cant_use):
	global graph
	global s
	distances = [float('inf') for _ in range(n+1)]
	distances[s] = 0
	
	queue = []
	heapq.heappush(queue, (0, s))
	
	while queue:
		current_distance, current_destination = heapq.heappop(queue)
		if current_destination == cant_use: continue
		
		if distances[current_destination] < current_distance: continue
		
		for next_destination, next_distance in graph[current_destination].items():
			if next_destination == cant_use: continue
			
			if distances[current_destination] + next_distance < distances[next_destination]:
				distances[next_destination] = distances[current_destination] + next_distance
				heapq.heappush(queue, (distances[current_destination] + next_distance, next_destination))
	
	return distances
	
for i in range(1, n+1):
	result = dijkstra(i)
	
	if result[e] == float('inf'): print(-1)
	else: print(result[e] + 1)