(백준) 최소 환승 경로 - 2021 [java]

https://www.acmicpc.net/problem/2021

 

🐢 설명

올리브영 코테에 나온 문제랑 비슷한 문제라서 풀게되었다.

 

출발 역과 도착 역이 주어지면 몇번 환승해서 도달할 수 있는지 알아내는 문제이다. 처음에는 문제가 잘 이해가 안되었는데 역 번호들이 나열된 하나의 행이 노선이라고 생각하면 된다.

 

구현

노선별 역을 담을 리스트와 역별로 자신을 지나가는 노선을 담을 리스트 두개를 만들어주었다.

방문체크 또한 해당 노선을 방문했는지 여부와 해당 역을 방문했는지 여부를 체크하기 위해 방문체크용 배열 두개를 만들어 주었다.

 

최소의 환승 횟수를 출력해야하므로 환승 횟수를 기준으로 갖는 우선순위큐를 사용했다.

 

주어진 출발역이 하나의 노선이 아니라 여러 노선에 담겨있을 수도 있으므로 라인 별로 해당 역을 우선순위큐에 넣어주고 각 라인들은 방문체크를 해주었다. 출발역 또한 방문체크를 해주었다.

 

이후 우선순위 큐에서 하나를 뽑으면 (현재 노선, 현재 역, 환승 횟수)를 갖고있는데 해당 역을 방문한적이 없다면 두가지 방법이 존재한다

1. 환승하지 않고 계속 가는방법
2. 환승하는 방법

따라서 이를 둘다 우선순위 큐에 담아주었다. 큐를 다 돌때까지 도착역을 만나지 못하면 -1을 출력하고, 만난다면 그때가 최소 환승 횟수를 가진 객체이므로 바로 출력하도록 했다.

 

🐢코드

public class 최소환승경로_2021 {
    static int N, M;
    static boolean[] visitedLine;
    static boolean[] visitedStation;
    static ArrayList<Integer>[] stations;
    static ArrayList<Integer>[] lines;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        visitedLine = new boolean[M + 1];
        visitedStation = new boolean[N + 1];
        stations = new ArrayList[N + 1];
        lines = new ArrayList[N + 1];
        for (int i = 1; i < N + 1; i++) {
            stations[i] = new ArrayList<>();
            lines[i] = new ArrayList<>();
        }

        for (int i = 1; i <= M; i++) {
            String[] s = br.readLine().split(" ");
            for (String station : s) {
                int statN = Integer.parseInt(station);
                if (statN == -1) break;
                stations[statN].add(i);
                lines[i].add(statN);
            }
        }

        st = new StringTokenizer(br.readLine());
        int start = Integer.parseInt(st.nextToken());
        int end = Integer.parseInt(st.nextToken());

        int answer = go(start, end);
        System.out.println(answer);
    }

    private static int go(int start, int end) {
        PriorityQueue<Node> pq = new PriorityQueue<>(Comparator.comparingInt(n -> n.transCount));
        visitedStation[start] = true;
        for (int line : stations[start]) {
            pq.add(new Node(line, start, 0));
            visitedLine[line] = true;
        }

        while (!pq.isEmpty()) {
            Node now = pq.poll();

            if (now.curStation == end) {
                return now.transCount;
            }

            for (int nextStation : lines[now.curLine]) {

                if (!visitedStation[nextStation]) {
                    visitedStation[nextStation] = true;
                    pq.add(new Node(now.curLine, nextStation, now.transCount));

                    for (int nextLine : stations[nextStation]) {
                        if (!visitedLine[nextLine]) {
                            visitedLine[nextLine] = true;
                            pq.add(new Node(nextLine, nextStation, now.transCount + 1));
                        }
                    }
                }
            }
        }
        return -1;
    }

    private static class Node {
        int curLine;
        int curStation;
        int transCount;

        public Node(int curLine, int curStation, int transCount) {
            this.curLine = curLine;
            this.curStation = curStation;
            this.transCount = transCount;
        }
    }
}

🐢 마무리

방문체크를 역과 노선을 구분해서 해주면 풀수있는 문제였다.