[백준] 18352 : 특정 거리의 도시 찾기 / python

1️⃣ 문제 설명

18352번: 특정 거리의 도시 찾기

어떤 나라에는 1번부터 N번까지의 도시와 M개의 단방향 도로가 존재한다. 모든 도로의 거리는 1이다.

이 때 특정한 도시 X로부터 출발하여 도달할 수 있는 모든 도시 중에서,

최단 거리가 정확히 K인 모든 도시들의 번호를 출력하는 프로그램을 작성하시오.

 

또한 출발 도시 X에서 출발 도시 X로 가는 최단 거리는 항상 0이라고 가정한다.

예를 들어 N=4, K=2, X=1일 때 다음과 같이 그래프가 구성되어 있다고 가정하자.

 

이 때 1번 도시에서 출발하여 도달할 수 있는 도시 중에서, 최단 거리가 2인 도시는 4번 도시 뿐이다.

2번과 3번 도시의 경우, 최단 거리가 1이기 때문에 출력하지 않는다.

 

2️⃣ 풀이 전 계획과 생각

문제는 다음과 같다.

⇒ 특정한 도시 X로부터 출발하여 도달할 수 있는 모든 도시 중에서, 최단 거리가 정확히 K인 모든 도시들의 번호를 출력하라.

그래프와 시작점이 주어졌을 때, 시작점에서 간선을 타고 이동할 수 있는 정점을 모두 찾아야 하는 문제이다.

시작점에서 모든 점까지의 최단거리를 구해줘야 한다.

BFS는 시작점에서 가까운 점들부터 탐색이 되기 때문에 최단거리를 구할 수 있다.

1. 방문하지 않았을 경우 방문처리 하고 그 위치까지의 거리를 +1을 해주자.
2. 목표 거리 K와 같아질 경우 → list에 추가하자.

• bfs (시작점에서 시작해서 갈 수 있는 정점들을 모두 탐색)
  • 초기화
    • 그래프 만들기
    • visited 배열 만들기
    • queue 만들기
  • 시작점 queue에 넣기
  • 시작점 방문처리하기
  • queue가 빌 때까지 반복(더 확인할 점이 없다면 정지)
    • queue에서 점 빼기
    • 해당 점에서 갈 수 있는 점들을 탐색
      • 이미 방문했던 점이면 무시
      • 아니면, queue에 추가
      • 방문처리한 배열 += 1 해주기

 

3️⃣ 막혔던 점과 고민

• 방향성이 있는 그래프다. 어떻게 그래프로 표현해줄까?
  • dictionary로 표현하여, 인접리스트를 구현하자.
  • graph[a].append(b)만 넣어주면 된다.

 

4️⃣ 1차 풀이

from collections import deque

def bfs(start):
    global visited;
    queue = deque([start])
    visited[start] = 1

    while queue:
        vertex = queue.popleft()
        for linked_vertex in graph[vertex]:
            if visited[linked_vertex] == 0:
                visited[linked_vertex] = visited[vertex] + 1

# init
vertex_num, edge_num, shortest_path, start = map(int, input().split())
graph = {vertex : [] for vertex in range(1, vertex_num+1)}
answer = []
for _ in range(edge_num):
    a, b = map(int, input().split())
    graph[a].append(b)
visited = [0] * (vertex_num + 1)

# 시작점 1 넣고, 탐색
bfs(1)

# 목표거리가 K인 경우, list에 추가
for vertex in range(len(visited)):
    if visited[vertex] == shortest_path:
        answer.append(vertex)

if len(answer) == 0:
    print(-1)
else:
    answer.sort()
    for vertex in answer:
        print(vertex)

 

5️⃣ 막혔던 점과 고민

🤔  잘못된 값이 나온다. 어디서 잘못해주었을까?

시작점은 1은 거리가 0이다.

visited를 0으로 초기화하면, 시작점에서 1로 시작한다.

visited를 -1로 초기화 해주자.

 

6️⃣ 2차 풀이

from collections import deque

def bfs(start):
    global visited;
    queue = deque([start])
    visited[start] = 0

    while queue:
        vertex = queue.popleft()
        for linked_vertex in graph[vertex]:
            if visited[linked_vertex] == -1:
                queue.append(linked_vertex)
                visited[linked_vertex] = visited[vertex] + 1

# init
vertex_num, edge_num, shortest_path, start = map(int, input().split())
graph = {vertex : [] for vertex in range(1, vertex_num+1)}
answer = []
for _ in range(edge_num):
    a, b = map(int, input().split())
    graph[a].append(b)
visited = [-1] * (vertex_num + 1)

# 시작점 넣고, 탐색
bfs(start)

# 목표거리가 K인 경우, list에 추가
for vertex in range(len(visited)):
    if visited[vertex] == shortest_path:
        answer.append(vertex)

if len(answer) == 0:
    print(-1)
else:
    for vertex in answer:
        print(vertex)

 

7️⃣ 막혔던 점과 고민

🤔 시간초과가 나온다. 어떻게 시간초과를 줄여줄 수 있을까?

🌟 파이썬의 경우 input().split()으로 하면 입력량이 많기 때문에 시간 초과가 난다.

sys.stdin.readline()을 사용해야 한다.

 

8️⃣ 3차 풀이

from collections import deque
import sys

def bfs(start):
    global visited;
    queue = deque([start])
    visited[start] = 0

    while queue:
        vertex = queue.popleft()
        for linked_vertex in graph[vertex]:
            if visited[linked_vertex] == -1:
                queue.append(linked_vertex)
                visited[linked_vertex] = visited[vertex] + 1

# init
input = sys.stdin.readline
vertex_num, edge_num, shortest_path, start = map(int, input().split())
graph = {vertex : [] for vertex in range(1, vertex_num+1)}
answer = []
for _ in range(edge_num):
    a, b = map(int, input().split())
    graph[a].append(b)
visited = [-1] * (vertex_num + 1)

# 시작점 넣고, 탐색
bfs(start)

# 목표거리가 K인 경우, list에 추가
for vertex in range(len(visited)):
    if visited[vertex] == shortest_path:
        answer.append(vertex)

if len(answer) == 0:
    print(-1)
else:
    for vertex in answer:
        print(vertex)

 

9️⃣ 풀이 후 알게된 개념과 소감

• 가중치가 없는 최단거리는 BFS 사용해서 구할 수 있다.
• 방향성이 있는 그래프면, 한쪽만 표현해주면 된다.
• 파이썬의 경우, 입력 값이 많은 경우,import sys
• input = sys.stdin.readline()을 사용하자.
• input() 함수를 사용하면 시간 초과를 경험한다.