알고리즘/백준
1261_알고스팟 **
베리영young
2024. 6. 23. 00:07
사용 알고리즘: 다익스트라
사용 언어: java
package week04;
import java.awt.Point;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Scanner;
import java.util.StringTokenizer;
public class Main_bj_1261_알고스팟 {
static int n, m, map[][], dp[][];
// static int ans; //최소 부숴야 할 벽 개수
static int[] dx = {1, 0}; //아래, 오른쪽으로만 가면 됨
static int[] dy = {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());
map = new int[n][m];
// ans = n * m;
for (int i = 0; i < n; i++) {
String s = br.readLine();
for (int j = 0; j < m; j++) {
//0: 빈 칸, 1: 벽
map[i][j] = s.charAt(j) - '0';
}
}
//데이크스트라라고 한다..
dp = new int[n][m];
for(int i=0; i<n; i++) {
Arrays.fill(dp[i], Integer.MAX_VALUE);
}
dp[0][0] = 0;
//입력 끝
dijkstra_1261();
System.out.println(dp[n-1][m-1]);
}
private static void dijkstra_1261() {
PriorityQueue<AlgoSpot> pq = new PriorityQueue<>((o1, o2) -> o1.move - o2.move);
boolean[][] visit = new boolean[n][m];
visit[0][0] = true;
pq.add(new AlgoSpot(new Point(0, 0), 0, 0));
while (!pq.isEmpty() ) {
AlgoSpot cur = pq.poll();
int x = cur.point.x;
int y = cur.point.y;
dp[x][y] = Math.min(dp[x][y], cur.crash);
if(cur.move >= n*m - 1) {
continue;
}
for (int d = 0; d < 2; d++) {
int nx = x + dx[d];
int ny = y + dy[d];
if(nx>=0 && ny>=0 && nx<n && ny<m && cur.move < n*m - 1) {
if(map[nx][ny] == 0) {
pq.add(new AlgoSpot(new Point(nx, ny), cur.move + 1, cur.crash));
}
else {
pq.add(new AlgoSpot(new Point(nx, ny), cur.move + 1, cur.crash + 1));
}
}
}
}
}
// private static int[][] copy_1261(int[][] map2) {
// int[][] map = new int[n][m];
//
// for (int i = 0; i < n; i++) {
// for (int j = 0; j < m; j++) {
// map[i][j] = map2[i][j];
// }
// }
// return map;
// }
}
class AlgoSpot {
Point point;
int move;
int crash;
// boolean[][] visit;
// int[][] map;
public AlgoSpot(Point point, int move, int crash) {
super();
this.point = point;
this.move = move;
this.crash = crash;
// this.visit = visit;
// this.map = map;
}
}
처음엔 bfs로 풀다가 , 이럴 거면 dp를 왜 만들었지! 했다.
여기서 dp는 [i][j] 위치로 갈 때까지 '부수는 벽의 최소 개수'를 의미한다.
그래서 우선순위 큐에서 poll할 때마다 dp[x][y] 값을 최소로 갱신한다.
..........
위의 코드는 메모리 초과가 난다.
주의 ** n과 m을 거꾸로 입력 받아야 한다....
통과된 코드
package week04;
import java.awt.Point;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Scanner;
import java.util.StringTokenizer;
public class Main_bj_1261_알고스팟 {
static int n, m, map[][], dp[][];
// static int ans; //최소 부숴야 할 벽 개수
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());
map = new int[n][m];
// ans = n * m;
for (int i = 0; i < n; i++) {
String s = br.readLine();
for (int j = 0; j < m; j++) {
//0: 빈 칸, 1: 벽
map[i][j] = s.charAt(j) - '0';
}
}
//데이크스트라라고 한다..
dp = new int[n][m];
for(int i=0; i<n; i++) {
Arrays.fill(dp[i], Integer.MAX_VALUE);
}
dp[0][0] = 0;
//입력 끝
dijkstra_1261();
System.out.println(dp[n-1][m-1]);
}
private static void dijkstra_1261() {
PriorityQueue<AlgoSpot> pq = new PriorityQueue<>((o1, o2) -> o1.move - o2.move);
boolean[][] visit = new boolean[n][m];
visit[0][0] = true;
pq.add(new AlgoSpot(new Point(0, 0), 0, 0));
while (!pq.isEmpty() ) {
AlgoSpot cur = pq.poll();
int x = cur.point.x;
int y = cur.point.y;
//메모리 초과
// dp[x][y] = Math.min(dp[x][y], cur.crash);
//
// if(cur.move >= n*m - 1) {
// continue;
// }
for (int d = 0; d < 4; d++) {
int nx = x + dx[d];
int ny = y + dy[d];
if(nx>=0 && ny>=0 && nx<n && ny<m && cur.move < n*m - 1) {
if(map[nx][ny] == 0) {
if (dp[nx][ny] > dp[x][y]) { //메모리 초과...
dp[nx][ny] = dp[x][y];
pq.add(new AlgoSpot(new Point(nx, ny), cur.move + 1, cur.crash));
}
// pq.add(new AlgoSpot(new Point(nx, ny), cur.move + 1, cur.crash));
}
else {
if (dp[nx][ny] > dp[x][y] + 1) {
dp[nx][ny] = dp[x][y] + 1;
pq.add(new AlgoSpot(new Point(nx, ny), cur.move + 1, cur.crash + 1));
}
// pq.add(new AlgoSpot(new Point(nx, ny), cur.move + 1, cur.crash + 1));
}
}
}
}
}
// private static int[][] copy_1261(int[][] map2) {
// int[][] map = new int[n][m];
//
// for (int i = 0; i < n; i++) {
// for (int j = 0; j < m; j++) {
// map[i][j] = map2[i][j];
// }
// }
// return map;
// }
}
class AlgoSpot {
Point point;
int move;
int crash;
// boolean[][] visit;
// int[][] map;
public AlgoSpot(Point point, int move, int crash) {
super();
this.point = point;
this.move = move;
this.crash = crash;
// this.visit = visit;
// this.map = map;
}
}
1. 시작점과 끝점이 항상 동일하니까, 오른쪽, 아래쪽으로만 움직이면 된다고 생각했는데, 예외가 있다.
0 0 1 0 0 0
1 0 0 0 1 0이런 경우, 위로 올라가야 부수는 벽의 개수를 최소화 할 수 있다
2. 메모리 초과!
시간초과를 고려하여 이런 걸 넣었는데, 핵심은 이게 아니었다고 한다..^^..
// dp[x][y] = Math.min(dp[x][y], cur.crash);
//
// if(cur.move >= n*m - 1) {
// continue;
// }메모리 초과는, 내가 설정해둔 pq의 크기가 너무 커지는 탓이었다.
그래서 add를 하는 순간에, dp값이 변경될 때만 add했어야 한다.