18352번 특정 거리의 도시 찾기
-
18352번 특정 거리의 도시 찾기알고리즘 2023. 2. 17. 13:30
문제 설명 이번 문제는 어떤 나라에서 단 방향 도로만 존재할 경우 주어진 도시 X에서 최단 거리 K만큼 떨어진 도시를 출력하는 문제입니다. 문제 풀이 아이디어 bfs 이번 문제는 한 노드에서 다른 노드로 가는 최단 거리를 구하는 문제이므로 bfs를 생각해낼 수 있습니다. 풀이 bfs 구현 (queue사용) queue를 통해 bfs를 구현해보도록 하겠습니다. queue의 원소는 도시 번호와 현재 이동 거리를 원소로 하는 배열이 됩니다. visited라는 배열을 둬서, 해당 도시를 방문했다면 visited[해당 도시]=True로 바꿔서 해당 도시를 최단거리로 방문했음을 알 수 있도록 해줍니다. 각 도시에 방문했을 경우, 해당 도시에서 단 방향 도로를 통해 갈 수 있는 도시 중 방문하지 않은 도시를 queue..
-
18352번 특정 거리의 도시 찾기알고리즘 2023. 2. 5. 11:24
문제 설명 이번 문제는 각 도시마다 다른 도시로 갈 수 있는 단 방향 도로가 존재할 경우, 주어진 도시 X에서 최단 거리 K로 갈 수 있는 도시를 출력하는 문제입니다. 문제 풀이 아이디어 bfs 최단거리로 갈 수 있다는 말을 보자마자 bfs를 떠올렸습니다. 풀이 변수 단방향 도로에 대한 정보를 저장할 roads dict를 선언했습니다. bfs를 이용한 풀이를 위해 우선 queue 배열을 선언했습니다. 그리고 원소는 [0, X]와 같은 형식으로 두었습니다. (0 => 현재 이동한 횟수, X => 현재 도시 ) 그리고 해당 도시를 방문했음을 알려주는 boolean 타입의 visited 배열을 선언해주었습니다. (visited의 원소는 False로 채워줍니다.) 결과값을 저장할 result 배열도 선언해주었습..