BOJ) 알고스팟 (1261 번)

알고스팟

1261번: 알고스팟

문제

 

벽이 존재하는 미로에서 처음 위치 (0,0)를 시작으로 (n-1,m-1)까지 도착해야한다.

이 때, 최소한으로 벽을 부시면서 경로를 찾는 문제다.

최소 + 경로 => 다익스트라를 이용하면 되겠다고 판단했다.

 

풀이

 

풀이는 간단하다.

일반적인 다익스트라를 구현하는 것 처럼 우선순위 큐를 활용해서 풀었다.

우선순위는 벽을 가장 적게 허문 순서대로 정렬했고, 이동하는 곳이 벽인 경우에는 +1을, 벽이 아닌 경우에는 +0을 해주며 길을 찾도록 설정했다.

각 weight(cost)가 0과 1이라는 것 이외에는 바로 전에 포스팅한 젤다 문제와 같았다.

 

코드

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
    final static char WALL = '1';
    final static int ADDITIONAL_NUM =1, ZERO =0;
    final static int[] dx = {0,0,1,-1}, dy = {1,-1,0,0};

    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());
        char[][] map = new char[m][n];

        for(int i=0; i<m; i++) {
            map[i] = br.readLine().toCharArray();
        }

        br.close();
        solution(n,m,map);
    }

    private static void solution(int n, int m, char[][] map) {
        int[][] dp = new int[m][n];
        for(int i=0; i<m; i++) {
            Arrays.fill(dp[i], Integer.MAX_VALUE);
        }
        dp[0][0] = ZERO;
        PriorityQueue<Pos> pq = new PriorityQueue<>();
        pq.offer(new Pos(0,0, dp[0][0]));

        while(!pq.isEmpty()) {
            Pos pos = pq.poll();

            for(int i=0; i<4; i++) {
                int nx = pos.x + dx[i];
                int ny = pos.y + dy[i];
                if(isInArea(nx,ny,n,m)) {
                    int addCount = map[ny][nx] == WALL ? ADDITIONAL_NUM : ZERO;
                    if(dp[ny][nx] > dp[pos.y][pos.x] + addCount) {
                        dp[ny][nx] = dp[pos.y][pos.x] + addCount;
                        pq.offer(new Pos(nx,ny, dp[ny][nx]));
                    }
                }
            }
        }

        System.out.println(dp[m-1][n-1]);
    }

    private static boolean isInArea(int x, int y, int n, int m) {
        return x>=0 && x<n && y>=0 && y<m;
    }

    private static class Pos implements Comparable<Pos>{
        int x,y,cost;

        public Pos(int x, int y, int cost) {
            this.x = x;
            this.y = y;
            this.cost = cost;
        }

        @Override
        public int compareTo(Pos pos) {
            return this.cost - pos.cost;
        }
    }
}