[백준] 1261 알고스팟 - Java

 

 

 

문제 출저

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

1261번: 알고스팟

 

 

 

문제 풀이 

세로 n, 가로 m인 2차원 배열이 주어지고 (1,1)에서 (n,m)으로 가야 합니다. 2차원 배열에는 벽이 1로 주어집니다. 이 때 최(n,m)으로 가기 위해 부숴야하는 최소한의 벽의 갯수를 구하는게 이 문제의 요구 사항 입니다. 

 

DP와 BFS로 풀었습니다. 

BFS로 Queue를 만들어 (1,1)을 시작점으로 하여 4방향 탐색을 시작했습니다. 

2차원 dp 배열을 만들어 (y,x) 지점에 도착할 때 필요한 부순 벽의 최솟값을 계속 업데이트 했습니다. 

현재 탐색 중에 부순 벽의 갯수가 dp에 저장된 벽에 갯수 보다 작아야 탐색을 계속 진행할 수 있는 겁니다. 

이런 식으로 dp 배열을 채워 dp (n,m)에 정답을 저장하게 하여 문제를 해결했습니다.

 

 

 

소스 코드 

package baekjoon.backjoon10.day2131.day21;


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

/*
알고스팟
https://www.acmicpc.net/problem/1261
 */
public class B1261 {

    static int n,m;
    static int[][] board;
    static int[][] dp;
    static int[] dx = {1,0,-1,0};
    static int[] dy = {0,-1,0,1};


    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        m = Integer.parseInt(st.nextToken());
        n = Integer.parseInt(st.nextToken());
        board = new int[n][m];
        for(int i = 0; i < n; i++) {
            String str = br.readLine();
            for(int j = 0; j < m; j++) {
                int number = Character.getNumericValue(str.charAt(j));
                board[i][j] = number;
            }
        }

        dp = new int[n][m];
        int large = n*m+1;
        for(int i = 0; i < n; i++) {
            Arrays.fill(dp[i], large);
        }

        Queue<dot> que = new LinkedList<>();
        dp[0][0] = 0;
        que.add(new dot(0, 0, 0));

        while (!que.isEmpty()) {
            dot d = que.poll();

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

                if(check(ny, nx)) {
                    int newCount = d.count;
                    if(board[ny][nx] == 1) {
                        newCount += 1;
                    }

                    if(dp[ny][nx] > newCount) {
                        dp[ny][nx] = newCount;
                        que.add(new dot(ny, nx, newCount));
                    }
                }
            }
        }

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

    }

    public static boolean check(int y, int x) {
        if(y >= 0 && y < n && x >= 0 && x < m) {
            return true;
        }
        else {
            return false;
        }
    }

    public static class dot {
        int y;
        int x;
        int count;

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