[TIL] 99클럽 코테 스터디 10일차 TIL + 백준 18352 특정 거리의 도시 찾기

 

문제 풀이

 

문제 탐색하기

알고리즘 파악하기

각 도시에서 갈 수 있는 도시들을 방문해가면서 처음 시작 도시에서의 거리를 측정해야하는 문제입니다.

도시에서 갈 수 있는 모든 도시들을 방문하는 것을 체크하면서 진행하기 위해서는 BFS 알고리즘이 적합하다는 것을 알 수 있습니다.

 

BFS 알고리즘으로 문제 풀이 설계하기

너비 우선 탐색(BFS, Breadth-First Search) 이란?

그래프 탐색 알고리즘으로, 너비를 우선으로 하여 탐색을 진행합니다. 시작 노드에서 가까운 노드를 우선적으로 탐색하며, 동일 레벨에 있는 노드를 모두 탐색한 후 다음 레벨로 넘어가는 방식입니다. BFS는 일반적으로 큐(Queue) 자료 구조를 사용하여 구현합니다.

 

따라서 출발지에서 방문할 수 있는 모든 도시를 방문하고 방문하지 않았던 도시는 큐에 추가하고 다음 레벨에서 dequeue과정을 통해서 다음 도시에서 방문할 수 있는 도시를 탐색하는 과정을 반복합니다. 이때, 도시를 방문할때마다 출발지로부터의 거리를 배열에 저장합니다. 

최종적으로 원하는 최단거리와 같은 거리를 저장한 도시를 출력해주면 되는 문제입니다.

 

여기서 주의할 점은 도로는 A -> B를 방문하는 단방향 도로임을 고려하여 문제를 풀어야합니다.

 

문제 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    static ArrayList<ArrayList> road = new ArrayList<>();
    static int[] distance;
    static boolean[] visited;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        int X = Integer.parseInt(st.nextToken());

        for(int i=0; i<=N; i++){
            road.add(new ArrayList());
        }

        distance = new int[N+1];
        visited = new boolean[N+1];

        for(int i=0; i<M; i++){
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            road.get(a).add(b);
        }

        for(int i=1; i<=N; i++){
            Collections.sort(road.get(i));
        }

        bfs(X);

        boolean print = false;
        for(int i=1; i<distance.length; i++){
            if(K == distance[i]){
                print = true;
                System.out.println(i);
            }
        }

        if(!print) System.out.println(-1);
    }

    private static void bfs(int start){
        visited[start] = true;
        Queue<Integer> queue = new LinkedList<>();
        queue.add(start);

        while(!queue.isEmpty()){
            int s = queue.poll();

            for(int i=0; i<road.get(s).size(); i++){
                int x = (int) road.get(s).get(i);
                if(!visited[x]){
                    queue.add(x);
                    visited[x] = true;
                    distance[x] = distance[s]+1;
                }
            }
        }
    }
}

 

 

오늘의 회고

오늘의 느낀점... 문제를 제대로 읽자

문제에서 단방향 도로가 존재한다는 정보를 제대로 읽지 않아서 계속 양방향 도로를 고집하며 문제를 풀다가 정답을 맞추지 못했습니다.

문제만 세세하게 읽었다면 풀 수 있었을 것 같아 아쉬웠습니다.. 흑흑