[자바] 백준 2206 - 벽 부수고 이동하기

ㅎㅎㅎㅎ메모리도 너무 많이 사용하고 속도도 느려서 이렇게 저렇게 나름 바꿔봤지만 변하지를 않았다. 속도는 그렇다 쳐도 메모리가 너무 의아했다. class하나 생성해서 큐에 집어넣어줘야 하나..?는 생각이 들었지만, 예전에 풀었던 소스도 int배열로 풀었는데 뭐가 문제지 고민했다. 

근데 방금 이유를 하나 찾아냈는데 너무 어이가 없다. BFS할 때 꼭 들어가는 dir[] 배열을 que안에서 매번 선언/생성하지 않고 que만 밖에다가 선언해서 썼더니 1/3이 줄었다 ㅎㅎ,,어이없네 

 

코드는 그냥 맨 처음 시도해서 성공한 코드라 최적화 전혀 안 되어 있다.

처음 시도할 때에는 틀렸었는데, 방문 여부를 부수고 들어왔을 때, 부수지 않고 들어왔을 때 나눠서 생각하지 않아서 틀렸다. 어차피 그 지점에 도착한 거면 상관없지 않나??라는 생각에 그랬는데, 다음에 또 부수고 갈 수 있냐 없냐의 차이가 발생하니까 꽤 큰 차이였다. 

/* 2020.12.12(토)*/
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

//동일한 좌표에 대해서, 벽을 부수고 온거랑 벽 부수지 않고 온거랑 방문여부 체크를 달리 해주어야 한다. 
public class Main{

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] str = br.readLine().trim().split(" ");
		int N = Integer.parseInt(str[0]);
		int M = Integer.parseInt(str[1]);
		
		int[][] map = new int[N][M];
		boolean[][][] visited = new boolean[2][N][M];
		
		for(int i=0;i<N;i++) {
			str = br.readLine().trim().split("");
			for(int j=0;j<M;j++) {
				map[i][j] = Integer.parseInt(str[j]);
			}
		}
		
		Queue<int[]> que = new LinkedList<int[]>();
		//n위치, m위치, 벽부실 수 있는 횟수, 횟수
		que.offer(new int[] {0,0,1,1});
		
		int[] tmp;
		int n,m,wall;
		int count=0;
		int newN,newM;
		boolean isArrived = false;
		while(!que.isEmpty()) {
			tmp = que.poll();
			n = tmp[0];
			m = tmp[1];
			wall = tmp[2];
			count = tmp[3];
			
			if(n==N-1 && m==M-1) {
				isArrived = true;
				break;
			}
			
			int[][] dir = {{1,0},{-1,0},{0,1},{0,-1}};
			for(int d=0;d<4;d++) {
				newN = n + dir[d][0];
				newM = m + dir[d][1];
				
				if(newN>=0 && newN<N && newM>=0 && newM<M) {
					
					if(map[newN][newM]==0 && !visited[wall][newN][newM]) {
						visited[wall][newN][newM] = true;
						que.offer(new int[] {newN,newM,wall,count+1});
					}
						
					else if(map[newN][newM]==1 && wall==1 && !visited[wall-1][newN][newM]) {
						visited[wall-1][newN][newM] = true;
						que.offer(new int[] {newN,newM,wall-1,count+1});
					}	
				}
			}
		}	
		if (isArrived) System.out.println(count);
		else System.out.println(-1);
	}
}