[BOJ]2206:벽 부수고 이동하기

최단 거리를 구해야하므로 BFS 문제이다.

처음에는 큐마다 방문 배열을 함께 넣어서 풀었었다.

static class Point {
		int x;
		int y;
		boolean wall;
		int[][] vis;

		public Point(int x, int y, boolean wall, int[][] vis) {
			this.x = x;
			this.y = y;
			this.wall = wall;
			this.vis = vis;
		}
	}
    
    
    // ...
    
    private static int bfs() {
     // ...
     
     Queue<Point> queue = new LinkedList<>();
     
     // ...
    }

 

하지만 N*M 최대가 1000 * 1000이다보니 배열을 계속 생성해서 메모리 초과가 난다.

그리고 처음에 메모리 초과가나는 이유가 궁금해서 찾다가 힌트를 봐버렸다....

 

좌표별로 벽을 부순적이 있는가 없는가로 구분되므로 매번 번거롭게 배열을 복제할 필요없고 visited[N][M][부순적이있는가]로 사용하면 메모리를 효율적으로 관리할수 있다.

 

https://github.com/SuyeonChoi/Algorithms/blob/master/BaekJoon/Java/BFS.DFS/p2206.java

GitHub - SuyeonChoi/Algorithms: Personal Algorithm Study::solving BOJ, Programmers, and SW Expert Academy