[백준] 2423번 전구를 켜라

문제 설명

• https://www.acmicpc.net/problem/2423
• Gold 1

문제 풀이

• 풀이때는 단순히 DP로 생각하여 풀었는데 풀고나니 다익스트라 알고리즘이라 놀랐다..
• 다익스트라 알고리즘으로 접근할 수 있다.
• 우선 격자의 모서리를 좌표로 고려하여 (0,0) -> (N,M)으로 가는 최단 거리를 생각한다.
• 최단 거리라고 표현한 것은 다익스트라 알고리즘을 고려한 워딩으로 여기서 거리란 필요한 회전수로 생각하면 된다.

소스 코드 (JAVA)

import java.io.*;
import java.util.*;

class Main {

    static BufferedReader br;
    static BufferedWriter bw;

    static class Point implements Comparable<Point>{
        int x, y, t;  // t: 회전 수

        public Point(int x, int y, int t) {
            this.x = x;
            this.y = y;
            this.t = t;
        }

        @Override
        public int compareTo(Point o) {
            return this.t - o.t;
        }
    }

    static int N, M;

    static int[][] map; // '\' : 0, '/' : 1
    static int[][] dp;
    static int[] dx = {-1, 1, 1, -1};
    static int[] dy = {1, 1, -1, -1};

    public static boolean needRotate(int x, int y, int d) {
        if (d == 0) return map[x-1][y] == 0;
        else if (d == 1) return map[x][y] == 1;
        else if (d == 2) return map[x][y-1] == 0;
        else return map[x-1][y-1] == 1;
    }

    public static void solve() throws IOException {
        PriorityQueue<Point> pq = new PriorityQueue<>();
        pq.add(new Point(0,0,0));
        dp[0][0] = 0;
        while(!pq.isEmpty()) {
            Point cur = pq.poll();
            if (cur.x == N && cur.y == M) break;
            for (int d = 0; d < 4; d++) {
                int X = cur.x + dx[d];
                int Y = cur.y + dy[d];
                if (X < 0 || Y < 0 || X > N || Y > M) continue;
                int nextT = needRotate(cur.x, cur.y, d) ? cur.t + 1 : cur.t;
                if (dp[X][Y] <= nextT) continue;
                dp[X][Y] = nextT;
                pq.add(new Point(X, Y, nextT));
            }
        }

        //결과 출력
        if (dp[N][M] == Integer.MAX_VALUE) bw.write("NO SOLUTION\n");
        else bw.write(dp[N][M] + "\n");
        bw.flush();
    }


    public static void input() throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        map = new int[N][M];
        dp = new int[N+1][M+1];
        for (int  i = 0; i < N+1; i++)
            Arrays.fill(dp[i], Integer.MAX_VALUE);
        for (int i = 0; i < N; i++) {
            String in = br.readLine();
            for (int j = 0; j < M; j++) {
                if (in.charAt(j) == '/') map[i][j] = 1;
                else map[i][j] = 0;
            }
        }
    }

    public static void main(String[] args) throws IOException {
        input();
        solve();
    }
}


/**
 * N * M ( 1<=N, M<=500)
 * dp[][] : 도달하기까지 최소 회전 수
 * pq : 회전수가 작은 것부터 뱉어냄
 *
 */