[백준] 1261 : 알고스팟 (JAVA)

문제

BOJ 1261 : 알고스팟 - https://www.acmicpc.net/problem/1261

풀이

벽을 최소 몇 개 부수어야 하는지를 구해야하기 때문에, 일단 BFS로 가능한 경로를 찾아야겠다고 생각했다.

[Queue의 넣는 조건]

1. 해당 위치에 한번도 방문하지 않았거나
2. 이전에 방문했지만 현재 방문하는 경우에서 부신 벽의 개수가 더 적을 경우

2번 조건을 확인하기 위해 map과는 별도로 부신 벽의 개수를 카운트하는 cnt 배열을 만들었다. 단순히 방문 여부 뿐만 아니라 숫자를 카운트 해야하기 때문에 -1로 초기화해서 방문하지 않음을 나타냈다.

코드

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

public class Main {

    static class Loc{
        int i;
        int j;
        int cnt;

        public Loc(int i, int j, int cnt) {
            this.i = i;
            this.j = j;
            this.cnt = cnt;
        }
    }

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

        int m = Integer.parseInt(inputs[0]);
        int n = Integer.parseInt(inputs[1]);

        int[][] map = new int[n + 1][m + 1];
        int[][] cnt = new int[n + 1][m + 1]; // memorization

        for (int i = 1; i <= n; i++) {
            String tmp = br.readLine();
            for (int j = 1; j <= m; j++) {
                map[i][j] = Integer.parseInt(String.valueOf(tmp.charAt(j-1)));
                cnt[i][j] = -1;
            }
        }

        Queue<Loc> queue = new LinkedList<>();
        queue.add(new Loc(1, 1, 0));
        cnt[1][1] = 0; // start point

        int[] mi = {0, 0, -1, 1};
        int[] mj = {1, -1, 0, 0};

        while (!queue.isEmpty()) {
            Loc now = queue.poll();

            for (int d = 0; d < 4; d++) {
                int ni = now.i + mi[d];
                int nj = now.j + mj[d];

                if (ni < 1 || ni > n || nj < 1 || nj > m) {
                    continue;
                }
                int tmp_cnt = now.cnt;
                if(map[ni][nj]==1){
                    tmp_cnt++;
                }
                
                if(cnt[ni][nj] == -1 || cnt[ni][nj]>tmp_cnt){
                    cnt[ni][nj] = tmp_cnt;
                    queue.add(new Loc(ni, nj, tmp_cnt));
                }

            }
        }

        System.out.println(cnt[n][m]);

    }
}

정리

✔ 알고리즘 분류 - 그래프 이론, 다익스트라, 0-1 너비 우선 탐색
✔ 난이도 - 🟡 Gold 4

🤦‍♀️ 오늘의 메모

• BFS는 조건을 어떻게 줄 것인지를 잘 생각해야 한다! 방문 여부만 확인해야하는 경우도 있고, 그 외의 것을 생각해야 하는 경우가 있으니 문제를 잘 읽어볼 것.

• 문제를 다 푼 후 찾아보니 Priority Queue나 Deque를 사용해서 풀이하는 방법도 있는거 같은데, 그것도 이후에 정리해보도록 하겠다.

참고 사이트

딱히 없음