[boj/java] 1261 알고스팟

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

내가 주의해야 하는 것

1. 문제 똑바로 읽기
- 이번엔 가로 M 과 세로 N 을 제대로 안봐서 뻘짓으로 시간 날렸다.

2. 문자열 입력은 기본으로 알고 있자
- 또 오랜만에 했더니 문자열 입력 받는데에서 헤맸다.. 이건 심했잖아!

import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;

class Point implements Comparable<Point> {
    int x;
    int y;
    int wall;
    Point(int y, int x, int wall) {
        this.y = y;
        this.x =x ;
        this.wall = wall;
    }

    @Override
    public int compareTo(Point o) {
        return wall - o.wall;
    }
}
public class Solution_1261 {

    static int[][] map;
    static int N, M;
    static int[] dx = {0, 0, -1, 1};
    static int[] dy = {-1, 1, 0, 0};
    static boolean[][] visited;

    public static int solution(int y, int x) {
        Queue<Point> q = new PriorityQueue<>();
        q.offer(new Point(y, x, map[y][x]));
        visited[y][x] = true;

        while(!q.isEmpty()) {
            Point p = q.poll();

            if(p.y == N-1 && p.x == M-1) {
                return p.wall;
            }

            for(int i=0; i<4; i++) {
                int ny = p.y + dy[i];
                int nx = p.x + dx[i];

                if(ny < 0 || nx < 0 || ny >=N || nx >= M)
                    continue;
                if(visited[ny][nx])
                    continue;
                if(map[ny][nx] == 0) {
                    q.add(new Point(ny, nx, p.wall));
                    visited[ny][nx] = true;
                } else {
                    q.add(new Point(ny, nx, p.wall+1));
                    visited[ny][nx] = true;
                }
            }
        }
        return 0;
    }


    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        M = sc.nextInt();
        N = sc.nextInt();
        sc.nextLine();


        map = new int[N][M];
        visited = new boolean[N][M];

        for(int i = 0; i < N; i ++) {
            String str = sc.nextLine();
            for(int j = 0; j <M; j ++) {
                map[i][j] = str.charAt(j)-'0';
                visited[i][j] = false;
            }
        }
        int ans = solution(0, 0);
        System.out.println(ans);
    }
}

우선순위 큐를 이용해서 벽이 없을때와 있을때가 공존할 경우, 벽이 없을때를 먼저 택하도록 하면, 최소로 벽을 몇개만 부숴야 하는 지 알 수 있다.

참고 : https://steady-coding.tistory.com/59