18352번 특정 거리의 도시 찾기

문제 설명

이번 문제는 어떤 나라에서 단 방향 도로만 존재할 경우 주어진 도시 X에서 최단 거리 K만큼 떨어진 도시를 출력하는 문제입니다.

 

 

문제 풀이

아이디어

bfs

이번 문제는 한 노드에서 다른 노드로 가는 최단 거리를 구하는 문제이므로 bfs를 생각해낼 수 있습니다.

 

풀이

bfs 구현 (queue사용)

queue를 통해 bfs를 구현해보도록 하겠습니다.

• queue의 원소는 도시 번호와 현재 이동 거리를 원소로 하는 배열이 됩니다.
• visited라는 배열을 둬서, 해당 도시를 방문했다면 visited[해당 도시]=True로 바꿔서 해당 도시를 최단거리로 방문했음을 알 수 있도록 해줍니다.
• 각 도시에 방문했을 경우, 해당 도시에서 단 방향 도로를 통해 갈 수 있는 도시 중 방문하지 않은 도시를 queue에 넣어주는 식으로 진행합니다.

 

 

해결

정답 비율에 비해 비교적 쉽게 풀 수 있었던 문제입니다.

 

문제 링크 : https://www.acmicpc.net/problem/18352

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

코드 링크 : https://github.com/beomseok37/baekjoon/blob/master/new!/18532.py