[백준] 1261번 : 알고스팟 - JAVA [자바]

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

---

bfs 알고리즘 문제이다.

[백준] 2178번 : 미로 탐색 - JAVA [자바]를 풀어봤다면 쉽게 풀 수 있다.

먼저 방의 정보(room)와 각 방을 가기 위해 부순 최소의 벽의 갯수를 저장한 배열(answer)과 각 방의 방문 여부(visited)를 저장하는 배열이 필요하다.

또한 방에서 상하좌우로 움직이기 위한 배열도 필요하고

int[] xMove = {0, 0, -1, 1};
int[] yMove = {-1, 1, 0, 0};

현재 좌표를 나타내기 위해 별도의 클래스도 정의하였다.

static class spot {
	int x;
    int y;

	spot(int x, int y) {
    	this.x = x;
        this.y = y;
	}
}

1. (0, 0) 부터 시작한다.
2. 인접한 방의 정보를 본다.
   2.1 벽이라면 부셔서 가야하므로 answer 배열에 전의 방까지 오면서 부순 벽의 갯수 + 1 을 저장한다.
   2.2 빈방이라면 그냥 가도 되므로 answer 에 전의 방까지 오면서 부순 벽의 갯수를 똑같이 저장한다.
   2.3 그 후 방문처리를 해주고 큐에 삽입한다.
3. 인접한 방을 탐색하다가 이미 방문한 방을 발견하면
   3.1 인접한 방이 벽이면 그 전에 방문했을 때 부순 벽의 갯수 answer[newX][newY]와 이번에 벽을 부셔서 방문했을 때의 answer[start.x][start.y] + 1 의 크기를 비교하고 만약 이번에 방문하는 것이 더 적은 갯수의 벽을 부셔서 가는 것이라면 answer 값을 변경하고 방문하는 방법이 달라졌으므로 큐에 삽입한다.
   3.2 인접한 방이 빈방이라면 그 전에 방문했을 때 부순 벽의 갯수 answer[newX][newY]와 이번에 그냥 방문 했을 때의 answer[start.x][start.y]의 크기를 비교하고 이번 방법이 더 적은 갯수의 벽을 부순다면 answer의 값을 업데이트하며 방법이 바꼈으므로 큐에 삽입한다.
4. 위의 방법을 큐가 빌때까지 반복하면 answer[N-1][M-1]의 값이 (n-1,m-1) 에 가는데 부순 벽의 최소 갯수가 된다.

여기서 주의할 점은 더 적은 갯수의 벽을 부셔서 가는 방법이 있어서 방법을 바꿨다면 큐에 삽입하여 이 방법으로 인해 생기는 방법들의 변화 또한 업데이트 해줘야 한다.

---

public class bj1261 {

    public static int M, N, count;
    public static int[][] room;
    public static int[][] answer;
    public static boolean[][] visited;
    static int[] xMove = {0, 0, -1, 1};
    static int[] yMove = {-1, 1, 0, 0};

    public static void main(String[] args) throws Exception {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] split = br.readLine().split(" ");
        M = Integer.parseInt(split[0]);
        N = Integer.parseInt(split[1]);

        visited = new boolean[N][M];
        room = new int[N][M];
        answer = new int[N][M];

        for (int i = 0; i < N; i++) {
            String line = br.readLine();
            char[] charArray = line.toCharArray();
            for (int j = 0; j < M; j++) {
                room[i][j] = Integer.parseInt(String.valueOf(charArray[j]));
            }
        }

        bfs(0, 0);

        bw.write(answer[N - 1][M - 1] + "\n");

        bw.flush();
        bw.close();
        br.close();
    }

    private static void bfs(int x, int y) {
        Queue<spot> queue = new LinkedList<>();
        queue.add(new spot(x, y));
        visited[x][y] = true;

        while (!queue.isEmpty()) {
            spot start = queue.poll();
            for (int i = 0; i < 4; i++) {
                int newX = start.x + xMove[i];
                int newY = start.y + yMove[i];

                if (newX >= 0 && newX < N) {
                    if (newY >= 0 && newY < M) {
                        // 아직 방문하지 않은 곳이라면
                        if (!visited[newX][newY]) {
                            if (room[newX][newY] == 1) {
                                answer[newX][newY] = answer[start.x][start.y] + 1;
                            } else answer[newX][newY] = answer[start.x][start.y];
                            queue.add(new spot(newX, newY));
                            visited[newX][newY] = true;
                        } // 방문했지만 벽을 더 적게 부수고 갈 수 있는 길이라면
                        else {
                            // 목적지가 벽을 부셔서 가야한다면
                            if (room[newX][newY] == 1) {
                                if (answer[newX][newY] > answer[start.x][start.y] + 1) {
                                    answer[newX][newY] = answer[start.x][start.y] + 1;
                                    queue.add(new spot(newX, newY));
                                }
                            } // 벽을 안부셔도 갈 수 있다면
                            else {
                                if (answer[newX][newY] > answer[start.x][start.y]) {
                                    answer[newX][newY] = answer[start.x][start.y];
                                    queue.add(new spot(newX, newY));
                                }
                            }
                        }
                    }
                }
            }

        }
    }

    static class spot {
        int x;
        int y;

        spot(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}