[BaekJoon] 2423 전구를 켜라 (Java)

1.  문제 링크

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

2.  문제

3.  소스코드

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

public class Main {
    static int row;
    static int col;
    static int min = Integer.MAX_VALUE;
    static List<Loc>[][] edges; // 각 위치에서 이동할 수 있는 위치들을 담는 List 배열

    static void input() {
        Reader scanner = new Reader();

        row = scanner.nextInt() + 1;
        col = scanner.nextInt() + 1;
        edges = new ArrayList[row][col];
        for(int r = 0; r < row; r++) {
            for(int c = 0; c < col; c++) {
                edges[r][c] = new ArrayList<>();
            }
        }

        for(int r = 0; r < row - 1; r++) {
            String info = scanner.nextLine();
            for(int c = 0; c < col - 1; c++) {
                char edgeDir = info.charAt(c);
                // 현재 (r, c)가 (2, 3)이라고 할 때,
                //  / 모양의 전선에서는
                //      - (2, 4) - (3, 3) 경로로 이동할 수 있다
                //      - 전선을 90도로 회전시킨다면 (2, 3) - (3, 4) 경로로 이동할 수 있다
                //      - 이를 (r, c)로 일반화시킨다면
                //          - (r, c + 1) - (r + 1, c) 경로에서는 회전수가 0
                //          - (r, c) - (r + 1, c + 1) 경로에서는 회전수가 1
                //  \ 모양의 전선에서는 위 일반화 식에서 회전수만 반대로 변경하면 된다
                // 이렇게 전선을 미리 모델링을 진행한다
                if(edgeDir == '/') {
                    edges[r][c + 1].add(new Loc(r + 1, c));
                    edges[r + 1][c].add(new Loc(r, c + 1));
                    edges[r][c].add(new Loc(r + 1, c + 1, 1));
                    edges[r + 1][c + 1].add(new Loc(r, c, 1));
                } else {
                    edges[r][c].add(new Loc(r + 1, c + 1));
                    edges[r + 1][c + 1].add(new Loc(r, c));
                    edges[r][c + 1].add(new Loc(r + 1, c, 1));
                    edges[r + 1][c].add(new Loc(r, c + 1, 1));
                }
            }
        }
    }

    static void solution() {
        // 모델링한 전선 정보를 통해 다익스트라 알고리즘을 이용하여 돌려야 하는 칸의 개수의 최솟값을 구한다
        dijkstra();
        System.out.println(min == Integer.MAX_VALUE ? "NO SOLUTION" : min);
    }

    static void dijkstra() {
        PriorityQueue<Loc> queue = new PriorityQueue<>(); // 돌린 칸의 개수를 기준으로 오름차순으로 정렬
        int[][] distance = new int[row][col]; // 각 위치까지 도달하는데 있어 돌려야 하는 칸의 개수의 최솟값
        for(int r = 0; r < distance.length; r++)
            Arrays.fill(distance[r], Integer.MAX_VALUE);

        queue.offer(new Loc(0, 0));
        distance[0][0] = 0;

        while(!queue.isEmpty()) {
            Loc cur = queue.poll();
            if(cur.x == row - 1 && cur.y == col - 1) { // 만약 전구가 있는 위치에 도달했다면
                // 돌린 칸의 개수를 기준으로 오름차순으로 정렬되어있기 때문에
                // 현재 돌린 칸의 개수가 최솟값이 될 것이므로 그 값을 min에 갱신하고 다익스트라 알고리즘을 끝낸다
                min = Math.min(min, cur.rotateNum);
                return;
            }
            // 이미 이전까지 구한 최솟값보다 현재 돌린 칸의 개수가 더 많다면
            // 이 이후로는 최솟값이 될 수 없으니 다음 경우를 확인한다
            if(distance[cur.x][cur.y] < cur.rotateNum) {
                continue;
            }

            // 이전까지의 최솟값과 다음 가려는 위치까지 돌린 칸의 개수를 비교하여 최솟값이 더 크다면
            // 이 경우는 최솟값이 될 수 있는 경우이므로 최솟값을 갱신하고 queue에 탐색을 위해 넣는다
            for(Loc next : edges[cur.x][cur.y]) {
                if(distance[next.x][next.y] > cur.rotateNum + next.rotateNum) {
                    distance[next.x][next.y] = cur.rotateNum + next.rotateNum;
                    queue.offer(new Loc(next.x, next.y, cur.rotateNum + next.rotateNum));
                }
            }
        }
    }

    static class Loc implements Comparable<Loc> {
        int x;
        int y;
        int rotateNum;

        public Loc(int x, int y) {
            this.x = x;
            this.y = y;
            this.rotateNum = 0;
        }

        public Loc(int x, int y, int rotateNum) {
            this.x = x;
            this.y = y;
            this.rotateNum = rotateNum;
        }

        @Override
        public int compareTo(Loc o) {
            return this.rotateNum - o.rotateNum;
        }
    }

    public static void main(String[] args) {
        input();
        solution();
    }

    static class Reader {
        BufferedReader br;
        StringTokenizer st;

        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while(st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }

            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }

            return str;
        }
    }
}