반응형
SMALL
특정 거리의 도시 찾기
-
18352번 특정 거리의 도시 찾기알고리즘 2023. 2. 5. 11:24
문제 설명 이번 문제는 각 도시마다 다른 도시로 갈 수 있는 단 방향 도로가 존재할 경우, 주어진 도시 X에서 최단 거리 K로 갈 수 있는 도시를 출력하는 문제입니다. 문제 풀이 아이디어 bfs 최단거리로 갈 수 있다는 말을 보자마자 bfs를 떠올렸습니다. 풀이 변수 단방향 도로에 대한 정보를 저장할 roads dict를 선언했습니다. bfs를 이용한 풀이를 위해 우선 queue 배열을 선언했습니다. 그리고 원소는 [0, X]와 같은 형식으로 두었습니다. (0 => 현재 이동한 횟수, X => 현재 도시 ) 그리고 해당 도시를 방문했음을 알려주는 boolean 타입의 visited 배열을 선언해주었습니다. (visited의 원소는 False로 채워줍니다.) 결과값을 저장할 result 배열도 선언해주었습..