반응형
SMALL
백준 18352
-
18352번 특정 거리의 도시 찾기알고리즘 2023. 2. 17. 13:30
문제 설명 이번 문제는 어떤 나라에서 단 방향 도로만 존재할 경우 주어진 도시 X에서 최단 거리 K만큼 떨어진 도시를 출력하는 문제입니다. 문제 풀이 아이디어 bfs 이번 문제는 한 노드에서 다른 노드로 가는 최단 거리를 구하는 문제이므로 bfs를 생각해낼 수 있습니다. 풀이 bfs 구현 (queue사용) queue를 통해 bfs를 구현해보도록 하겠습니다. queue의 원소는 도시 번호와 현재 이동 거리를 원소로 하는 배열이 됩니다. visited라는 배열을 둬서, 해당 도시를 방문했다면 visited[해당 도시]=True로 바꿔서 해당 도시를 최단거리로 방문했음을 알 수 있도록 해줍니다. 각 도시에 방문했을 경우, 해당 도시에서 단 방향 도로를 통해 갈 수 있는 도시 중 방문하지 않은 도시를 queue..