1️⃣ 문제 설명
어떤 나라에는 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을 해주자.
- 목표 거리 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() 함수를 사용하면 시간 초과를 경험한다.
'Problem Solving' 카테고리의 다른 글
[프로그래머스] 튜플 (2019 KAKAO INTERNSHIP) / python (0) | 2022.02.06 |
---|---|
[백준] 1753 : 최단경로 / python (0) | 2022.02.05 |
[프로그래머스] 정수 삼각형 / python (0) | 2022.02.03 |
[백준] 1463 : 1로 만들기 / python (0) | 2022.02.02 |
[백준] 10819 : 차이를 최대로 / python (0) | 2022.01.25 |