18352번 특정 거리의 도시 찾기

문제 설명

이번 문제는 각 도시마다 다른 도시로 갈 수 있는 단 방향 도로가 존재할 경우, 주어진 도시 X에서 최단 거리 K로 갈 수 있는 도시를 출력하는 문제입니다.

 

문제 풀이

아이디어

bfs

최단거리로 갈 수 있다는 말을 보자마자 bfs를 떠올렸습니다.

 

 

풀이

변수

단방향 도로에 대한 정보를 저장할 roads dict를 선언했습니다.

bfs를 이용한 풀이를 위해 우선 queue 배열을 선언했습니다.

그리고 원소는 [0, X]와 같은 형식으로 두었습니다. (0 => 현재 이동한 횟수, X => 현재 도시 )

그리고 해당 도시를 방문했음을 알려주는 boolean 타입의 visited 배열을 선언해주었습니다. (visited의 원소는 False로 채워줍니다.)

결과값을 저장할 result 배열도 선언해주었습니다.

 

단방향 도로 저장

문제에서 주어진 도로 (A B => A에서 B로 가는 단방향 도로가 존재)를 통해 roads에 key값 A의 원소가 존재하지 않을 경우 원소로 배열을 선언한 뒤 roads[a]에 B를 넣어줍니다.

주어진 도로에 대해서 위의 과정을 반복합니다.

 

bfs

queue에 원소가 없을 때 break되는 while문을 통해 반복합니다.

queue에서

dequeue된 원소의 현재 이동 횟수가 K가 아닐 경우에 원소의 현재 도시에서 갈 수 있는 도시 중 방문하지 않은 곳을 queue에 같은 형식([이동한 횟수, 이동한 도시])의 원소를 enqueue시켜줍니다. (이동한 도시 또한 visited 배열 값을 True로 바꿔줍니다.)

dequeue된 원소의 현재 이동 횟수가 K일 경우 result 배열에 현재 도시를 넣어줍니다.

 

 

 

해결

이번 문제는 dfs를 이용한 풀이를 생각해 냈다면 바로 풀 수 있는 문제였습니다.

 

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

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

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