[백준] 1261 알고스팟 java

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

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

public class AlgoSpot {
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static BufferedReader br;
    static StringTokenizer st;
    static int n, m;
    static int[][] board;
    static int[][] dp;

    public static void main(String[] args) throws IOException{
        input();
        System.out.println(bfs(0, 0));
    }

    static void input() throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        st = new StringTokenizer(br.readLine());
        m = Integer.parseInt(st.nextToken());
        n = Integer.parseInt(st.nextToken());
        board = new int[n][m];
        dp = new int[n][m];
        for(int i = 0; i < n; i++) {
            char[] tmp = br.readLine().toCharArray();
            for(int j = 0; j < m; j++) {
                board[i][j] = tmp[j] - '0';
            }
        }

        for(int[] arr : dp) {
            Arrays.fill(arr, Integer.MAX_VALUE);
        }
        dp[0][0] = 0;
    }

    static int bfs(int x, int y) {
       Deque<Point_1> q = new LinkedList<>();
       q.offer(new Point_1(x, y));
       while(!q.isEmpty()) {
           Point_1 cur = q.poll();
           for(int i = 0; i < 4; i++) {
               int xx = cur.x + dx[i];
               int yy = cur.y + dy[i];

               if(xx < 0 || yy < 0 || xx >= n || yy >= m) continue;


               if (dp[cur.x][cur.y] + board[xx][yy] < dp[xx][yy]) {
                   dp[xx][yy] = dp[cur.x][cur.y] + board[xx][yy];
               }
               else continue;

               if(board[xx][yy] == 0) q.addFirst(new Point_1(xx, yy));
               if(board[xx][yy] == 1) q.addLast(new Point_1(xx, yy));
           }
       }
       return dp[n-1][m-1];
    }
}

우선순위 큐 또는 덱을 이용한 bfs 문제였다. 

 

0-1 bfs란 것을 이번에 또 배웠다. 단순히 BFS를 하는게 아니라 메모이제이션을 활용해서 벽을 부셔온 비용을 갱신하고 또 가중치에 따라서 0이면 큐에 앞에넣고 1이면 큐의 뒤에 넣는 방식으로 최단거리를 구할 수 있었다.

 

시간복잡도 면에서도 다익스트라를 사용한다면 O(E log E) 또는 O(E log V) 이지만 0-1 BFS를 사용하면 특정 간선을 두번 이상 지나가는 경우가 없기 때문에 O(E)에 특정 노드도 2번 이상 경유하는 경우가 없으므로 O(V)이다. 그래서 O(V) + O(E) 이므로 시간복잡도는 O(V+E)까지 줄게 된다.

 

0-1 BFS 구현

 

1. 덱에서 노드를 꺼낸다.

 

2. 인접한 노드를 살핀다.

 

3. 현재 노드까지 소비된 비용 + 그 노드를 향하는 가중치 < 그 노드까지 가는데 소비된 비용이면 DP를 갱신해준다.

 

4. 노드가 갱신된 상태에서 그 노드의 가중치가 0이면 덱의 front에 넣고 1이면 덱의 back에 삽입하도록 한다.

 

5. 덱에서 깨낼 노드가 없을 때까지 반복한다.