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. 덱에서 깨낼 노드가 없을 때까지 반복한다.
'Dev > PS' 카테고리의 다른 글
[백준] 7453 합이 0인 네 정수 java (0) | 2022.04.14 |
---|---|
[백준] 1208 부분수열의 합 2 java (0) | 2022.04.12 |
[백준] 1806 부분합 java (0) | 2022.03.30 |
[백준] 2580 스도쿠 java (0) | 2022.03.27 |
[백준] 5014 스타트링크 java (0) | 2022.03.25 |