백준 1261번 : 알고스팟 java

이 문제는 벽을 최대한 적게 부수면서 (1, 1)에서 (N, M)까지 갈 때 부순 벽의 개수를 출력하는 문제입니다.

이 문제를 언뜻 보았을 때 dfs를 이용해서 벽을 부수면서 탐색해야 할 것처럼 보입니다.

하지만 이 문제는 끝까지 갔을 때 부순 벽의 개수가 최소가 되어야합니다.

따라서 bfs를 이용해서 주변을 탐색하며 끝까지 가장 벽을 적게 부수고 가는 경우의 수를 찾아야 합니다.

이를 위해서 PriorityQueue에 각각의 노드의 정보와 벽을 몇 개를 부수었는지에 대한 정보를 넣고 벽을 부신 개수를 오름차순으로 정렬하여 벽을 가장 적게 부수고 끝 점까지 가는 방법을 찾아야 합니다.

이에 대한 코드를 보여드리도록 하겠습니다.

---

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


public class Main {
    static int row, col;
    static int[][] map;
    static boolean[][] visited;
    static int[] dR = {1, -1, 0, 0};
    static int[] dC = {0, 0, 1, -1};

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        col = Integer.parseInt(st.nextToken());
        row = Integer.parseInt(st.nextToken());

        map = new int[row][col];
        visited = new boolean[row][col];

        for(int i = 0; i<row; i++){
            String[] input = br.readLine().split("");

            for(int j = 0; j<col; j++)
                map[i][j] = Integer.parseInt(input[j]);
        }

        System.out.println(pathFind(0, 0));
    }

    static int pathFind(int startRow, int startCol){
        Queue<Node> q = new PriorityQueue<>();
        q.offer(new Node(startRow, startCol, 0));
        visited[startRow][startCol] = true;

        while(!q.isEmpty()){
            Node a = q.poll();

            if(a.row == row-1 && a.col == col-1) {
                return a.breakWall;
            }

            for(int i = 0; i<4; i++){
                int dr = a.row + dR[i];
                int dc = a.col + dC[i];

                if(dr<0||dc<0||dr>=row||dc>=col)
                    continue;
                if(visited[dr][dc])
                    continue;

                if(map[dr][dc] == 0)
                    q.offer(new Node(dr, dc, a.breakWall));
                else
                    q.offer(new Node(dr, dc, a.breakWall+1));

                visited[dr][dc] = true;
            }
        }

        return 0;
    }
}
class Node implements Comparable<Node>{
    int row, col, breakWall;

    Node(int row, int col, int breakWall){
        this.row = row;
        this.col = col;
        this.breakWall = breakWall;
    }

    @Override
    public int compareTo(Node a){
        return this.breakWall - a.breakWall;
    }
}

위에 설명드린 대로 문제를 해결하면 되는 bfs문제였습니다.