MoveCrashingWall

문제 복기

최근 BFS/DFS 같은 그래프 탐색 문제에서 클래스를 정의하는 색다른 방법을 알게 됐다. x,y좌표 뿐만 아니라 시작좌표에서 (x,y)좌표까지의 거리 dist와 문제에 따라 필요한 정보를 함께 속성으로 정의해주고 저장해주는 것이다!

알고리즘 생각 - 각 좌표마다 드릴 횟수를 저장하는 정수형 2차원 배열을 생성해서 초기값은 -1 또는 무한대값으로 초기화해준다. 상하좌우를 탐색하면서 방문하나 노드는 드릴 횟수를 저장해준다. 만약 큐에서 꺼낸 현재 좌표의 드릴 횟수보다 탐색할 다음 노드의 좌표 드릴 횟수(visit[nx][ny] = Integer.MAX_VALUE)가 작거나 같으면 다음 노드 좌표를 큐에 넣지 않는다.? =>방문한 노드이기 때문에 큐에 다시 넣지 않는 맥락인듯. 일종의 중복 방문 방지. 아닌가?

입력받는 수 범위가 1000으로 꽤나 크기 때문에 시간 초과나 메모리 초과에 특히 더 유의해야 한다!

메모리 초과 방지를 위한 중요한 부분

if(visit[nx][ny]<=cur.drill)continue;

import java.util.Queue;
import java.util.LinkedList;
import java.io.BufferedReader;
import java.io.InputStreamReader;
class MCW {
	int x,y,dist,drill;
	MCW(int x,int y,int dist,int drill){
		this.x = x;
		this.y = y;
		this.dist = dist;
		this.drill = drill;
	}
}
public class MoveCrashingWall {
	public static final int max = Integer.MAX_VALUE;
	public static int n,m,ans;
	public static int[][] map,visit;
	public static int[] dx = {-1,1,0,0};
	public static int[] dy = {0,0,-1,1};
	public static void bfs(int x,int y) {//(0,0)에서 시작, (n-1,m-1)까지 d배열 완성.
		Queue<MCW>  q = new LinkedList<MCW>();
		q.add(new MCW(x,y,1,0));//x,y,dist,drill
		visit[x][y] = 0;//드릴 횟수 0.
		while(!q.isEmpty()) {
			MCW cur = q.remove();
			if(cur.x == n-1 && cur.y == m-1) {
				ans = cur.dist;
				break;
			}
			for(int i=0;i<4;i++) {
				int nx = cur.x+dx[i];//지금 필요한 건 nx와 ny인데, 
				int ny = cur.y+dy[i];
				if(nx<0 || nx>n-1 || ny<0 || ny>m-1)continue;
				//if(visit[nx][ny]<=visit[cur.x][cur.y])continue;
				if(visit[nx][ny]<=cur.drill)continue;
				if(map[nx][ny]==0) {//벽이 아닌 경우.
					visit[nx][ny] = cur.drill;//현재의 드릴 횟수 저장.
					q.add(new MCW(nx,ny,cur.dist+1,cur.drill));
				}
				else {//벽인 경우.
					if(cur.drill == 0) {
						visit[nx][ny] = cur.drill+1;
						q.add(new MCW(nx,ny,cur.dist+1,cur.drill+1));
					}
				}
			}
		}
	}
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] input = br.readLine().split(" ");
		n = Integer.parseInt(input[0]);
		m = Integer.parseInt(input[1]);
	    map = new int[n][m];
		visit = new int[n][m];
		
	    for (int i=0; i<n; i++) {
	    	input = br.readLine().split("");
	        for (int j=0; j<m; j++) {
	            map[i][j] = Integer.parseInt(input[j]);
	            visit[i][j] = max;
	        }
	    }
	    ans = max;
		bfs(0,0);
		if(ans == max) System.out.println(-1);
		else System.out.println(ans);
	}

}