[Python] BOJ(백준) 18352번 - 특정 거리의 도시 찾기

1. 링크

https://www.acmicpc.net/problem/18352

2. 난이도(solved.ac 참고)

실버2

3. 풀이 1: BFS 활용

	# https://www.acmicpc.net/problem/18352
	from collections import deque
	import sys
	f = sys.stdin.readline
	n, m, k, x = map(int, f().split())
	graph = [[] for _ in range(n+1)]
	distance = [0] * (n+1)
	visited = [False] * (n+1)
	for _ in range(m):
	a, b = map(int, f().split())
	graph[a].append(b)
	def bfs(start):
	answer = []
	q = deque([start])
	visited[start] = True
	distance[start] = 0
	while q:
	now = q.popleft()
	for i in graph[now]:
	if not visited[i]:
	visited[i] = True
	q.append(i)
	distance[i] = distance[now] + 1
	if distance[i] == k:
	answer.append(i)
	if len(answer) == 0:
	print(-1)
	else:
	answer.sort()
	for i in answer:
	print(i, end='\n')
	bfs(x)

view raw 특정거리의도시찾기(BFS).py hosted with ❤ by GitHub

일반적인 BFS문제와 같으나 방문하지 않았을 경우 방문처리 하고 그 위치까지의 거리를 +1을 해준다. 그 뒤 +1해준 거리가 목표 거리 K와 같아질 경우 answer라는 리스트에 넣은 뒤 오름차순으로 정렬하고 while문 밖 if문에서 프린트 해주도록 했다.

 

4. 풀이 2: 다익스트라 알고리즘 활용

	# https://www.acmicpc.net/problem/18352
	import heapq
	import sys
	f = sys.stdin.readline
	INF = int(1e9)
	n, m, k, x = map(int, f().split())
	graph = [[] for _ in range(n+1)]
	distance = [INF] * (n+1)
	for _ in range(m):
	a, b = map(int, f().split())
	graph[a].append((b, 1))
	def dijkstra(start):
	q = []
	heapq.heappush(q, (0, start))
	distance[start] = 0
	while q:
	dist, now = heapq.heappop(q)
	if distance[now] < dist: continue
	for j in graph[now]:
	cost = dist + j[1]
	if cost < distance[j[0]]:
	distance[j[0]] = cost
	heapq.heappush(q, (cost, j[0]))
	dijkstra(x)
	answer = []
	for i in range(1, n+1):
	if distance[i] == k: answer.append(i)
	if len(answer) == 0: print(-1)
	else:
	for i in answer: print(i, end='\n')

view raw 특정거리의도시찾기(다익스트라).py hosted with ❤ by GitHub

13행 for문 내부 append에서 가중치를 1로 두고 넣었다. 거리와 현재 노드의 위치를 순서대로 힙에서 빼낸 뒤 cost에 현재까지의 거리(dist) + 가중치 를 넣는다. 여기서는 가중치가 1이므로 +1씩만 더해졌다. 현재 distance의 기본값이 10^9이므로 모든 위치에 대해 10^9보다는 당연히 cost가 더 작을 것이다. 이 값을 반영해준다. 그리고 현재까지의 cost(거리+가중치 1)와 j[0](해당 노드의 위치)을 힙에 넣어주는 방식으로 진행을 한다.

 

while문을 마치고 나면 각 노드까지의 최단 경로의 길이가 출력이 되는데, 이 값이 우리가 미리 input으로 넣어둔 k와 같은지 여부를 확인한 뒤 같으면 answer라는 리스트에 넣은 뒤 오름차순으로 정렬하고 while문 밖 if문에서 프린트 해주도록 했다.