문제링크는 아래에서 확인해주세요!
https://www.acmicpc.net/problem/18352
접근 방법
- 일단 최단 경로를 구하는 문제고 모든 간선의 크기는 1로 동일하기 때문에
BFS알고리즘을 사용하기로 결정 - BFS를 사용해야 하기 때문에 내장 라이브러리인
deque사용 - 빠른 입력을 하기 위해서
input = sys.stdin.readline설정 - 방문 표시를 위해 distances 변수 사용
Code
import sys
from collections import deque
input = sys.stdin.readline
N, M, K, X = map(int, input().split())
city = [[] for _ in range(N+1)]
# 그래프 초기 설정
for _ in range(M):
a, b = map(int, input().split())
city[a].append(b)
# 최단 거리 표시 초기 설정
distances = [-1] * (N+1)
distances[X] = 0
queue = deque([X]) # BFS를 위해 초기 큐 설정
while queue:
node = queue.popleft()
for next in city[node]:
if distances[next] == -1: # 방문한 적이 없는 노드인경우
distances[next] = distances[node] + 1
queue.append(next)
isFind = False
for idx in range(1, N+1):
if distances[idx] == K:
print(idx)
isFind = True
if isFind == False:
print(-1)- 주어진 정보를 가지고 그래프를 초기 설정을 해줌
- 방문 표시를 위해 모든 노드의 최단 거리를 -1으로 초기화. 즉 해당 노드의 방문 정보가 -1이면 아직 방문을 한 적이 없다는 의미임.
- 시작 노드는 방문 표시를 위해 0으로 초기화
- BFS 알고리즘을 사용하기 때문에 시작 노드를 포함시켜서 queue 생성
- queue에서 첫 번째 노드번호를 뽑아와서 해당 노드에 인접한 노드를 순회한다.
- 순회하면서 distance[노드번호]가 -1이 아닌 경우에는 탐색을 하지 않는다. 이유는 distance 변수는 시작노드로 부터 각 노드에 대한 최단거리 정보이다. 따라서 이미 방문한 경우에는 굳이 또 탐색을 할 필요가 없다. 이미 최단 경로로 설정이 되어있기 때문이다.
- -1인 경우에는 이전 노드까지의 거리에다가 1을 더해주면 된다. 그리고 queue에 넣어준다. 또 탐색을 해야하니까!
- 탐색이 모두 끝난 후에는 distance 변수에 최단거리 정보가 남아있을 것이다. 순회를 하면서 문제에서 주어진 K와 값이 동일하면 출력만 하면 된다.
후기
일단 혼자서 풀지 못했다. 구글링을 통해 코드 참조를 좀 했다.
BFS와 DFS를 머릿속에서 떠올리기가 아직 좀 많이 어려운 것 같다.
그리고 언제 BFS를 써야하고 언제 DFS를 써야하는지 항상 헷갈리는데 나름 괜찮은 자료를 가져와봤다. 틈틈히 찾아서 보자.
그리고 코딩테스트 공부를 사실 나는 굳이 할 필요는 없다. 아니 굳이 할 필요 없다기 보다는 코딩테스트 보다 내 백엔드 개발 역량 향상에 더욱 집중을 해야하긴 하지만 하루에 일어나서 1문제씩 푸는건 사실 뭐..ㅎ 그냥 매일매일 1문제씩 풀면서 엉켜있는 내 머리 푼답시고.. 열심히 해보자! (사실 조만간 코테하나 있어서 부랴부랴 하는것도..ㅎ)
아래 링크는 BFS와 DFS를 비교한 자료입니다!
https://ardentdays.tistory.com/11
Reference
블로그 이전했습니다!! https://dev-iamkanguk.tistory.com/ <<- 여기로 오세용!!