[Java][2206] 벽 부수고 이동하기

문제:

https://www.acmicpc.net/problem/2206

2206번: 벽 부수고 이동하기

첫시도:

import java.util.*;

public class Main {
	public static int [][] dist = new int[1002][1002];
	public static int [][] board = new int[1002][1002];
	public static int [] dx = {1,0,-1,0};
	public static int [] dy = {0,1,0,-1};
	public static int n,m;
    public static void main(String[] args){
    	Scanner sc = new Scanner(System.in);
    	n = sc.nextInt();
    	m = sc.nextInt();
    	
    	Queue<Pos> q1 = new LinkedList(); // 이동용
    	Queue<Pos> q2 = new LinkedList(); // 벽 제거
    	
    	for(int i=0;i<n;i++) {
    		String s = sc.next();
    		for(int j=0;j<m;j++) {
    			board[i][j] = s.charAt(j)-'0';
    			if(s.charAt(j) == '1') {
    				q2.add(new Pos(i,j)); // 모든 벽 위치
    			}
    		}
    	}
    	for(int i=0;i<n;i++) {
    		for(int j=0;j<m;j++) {
    			dist[i][j] = -1;
    		}
    	}
    	
    	dist[0][0] = 0;
    	q1.add(new Pos(0,0));
    	
    	int min = Integer.MAX_VALUE;
    	while(!q2.isEmpty()) {
    		Pos cur2 = q2.poll(); // 벽 위치
    		board[cur2.x][cur2.y]= 0;
    		while(!q1.isEmpty()) {
    			Pos cur1 = q1.poll();
    			for(int dir = 0;dir<4;dir++) {
    				int nx = cur1.x+dx[dir];
    				int ny = cur1.y+dy[dir];
    				if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
    				if(dist[nx][ny] >= 0 || board[nx][ny] == 1) continue;
    				dist[nx][ny] = dist[cur1.x][cur1.y]+1;
    				q1.add(new Pos(nx,ny));
    			}
    		}
    		if(dist[n-1][m-1] != -1) {
    			min = Math.min(min, dist[n-1][m-1]);
    		}
    		
    		for(int i=0;i<n;i++) {
        		for(int j=0;j<m;j++) {
        			dist[i][j] = -1;
        		}
        	}
        	
        	dist[0][0] = 0;
        	q1.add(new Pos(0,0));
        	board[cur2.x][cur2.y]= 1;
    	}
    	
    	if(min == Integer.MAX_VALUE) {
    		System.out.println(-1);
    	}else {
    		System.out.println(min+1);
    	}
    }
}

class Pos{
	int x;
	int y;
	
	Pos(int x, int y){
		this.x = x;
		this.y = y;
	}
}

 

모든 벽에 대해서 한번씩 제거하고 거리를 측정하는 경우 (시간초과)

 

import java.util.*;

public class Main {
	public static int [][][] dist = new int[1002][1002][2];
	public static int [][] board = new int[1002][1002];
	public static int [] dx = {1,0,-1,0};
	public static int [] dy = {0,1,0,-1};
	public static int n,m;
    public static void main(String[] args){
    	Scanner sc = new Scanner(System.in);
    	n = sc.nextInt();
    	m = sc.nextInt();
    	
    	Queue<Pos> q = new LinkedList(); // 이동용
    	
    	for(int i=0;i<n;i++) {
    		String s = sc.next();
    		for(int j=0;j<m;j++) {
    			board[i][j] = s.charAt(j)-'0';
    		}
    	}
    	
    	for(int i=0;i<n;i++) {
    		for(int j=0;j<m;j++) {
    			dist[i][j][0] = -1;
    			dist[i][j][1] = -1;
    		}
    	}
    	
    	dist[0][0][0] = 1;
    	dist[0][0][1] = 1;
    	q.add(new Pos(0,0,0));
    	
    	int ans = -1;
    	while(!q.isEmpty()) {
    		Pos cur = q.poll();
    		if(cur.x == n-1 && cur.y == m-1) {
    			ans = dist[cur.x][cur.y][cur.z];
    			break;
    		}
    		for(int dir = 0;dir<4;dir++) {
    			int nx = cur.x+dx[dir];
    			int ny = cur.y+dy[dir];
    			if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
    			if(dist[nx][ny][cur.z] >= 0) continue;
    			if(board[nx][ny] == 0) {
    				dist[nx][ny][cur.z] = dist[cur.x][cur.y][cur.z]+1;
    				q.add(new Pos(nx,ny,cur.z));
    			}else {
    				if(cur.z == 1) continue;
    				dist[nx][ny][1] = dist[cur.x][cur.y][cur.z]+1;
    				q.add(new Pos(nx,ny,1));
    			}
    			
    		}
    	}
    
    	System.out.println(ans);
    }
}

class Pos{
	int x;
	int y;
	int z;
	
	Pos(int x, int y,int z){
		this.x = x;
		this.y = y;
		this.z = z;
	}
}

 

벽을 부숴서 진행한 경우(dist[i][j][1]) 와 벽을 부숴서 진행하지 않은 경우(dist[i][j][0])를 3차원 배열로 나누어 계산

 

다양한 벽을 부수는 경우의 수가 있음에도 불구하고 3차원 배열로 두 가지로 나누어 계산할 수 있는 이유는

목적지에 최단거리로 도착한 순간 반복문을 종료하기 때문이다.

 

예시)

8 7
0000000
1111110
0100010
0101000
0101111
0100000
0111110
0000000

인 경우

 

dist[i][j][0] (벽을 부수지 않은 경우) (답이 출력된 순간)

1 2 3 4 5 6 7 
-1 -1 -1 -1 -1 -1 8 
-1 -1 -1 14 13 -1 9 
-1 -1 -1 -1 12 11 10 
-1 -1 -1 -1 -1 -1 -1 
-1 -1 -1 -1 -1 -1 -1 
-1 -1 -1 -1 -1 -1 -1 
-1 -1 -1 -1 -1 -1 -1

dist[i][j][1] (벽을 부순 경우)

1 4 5 6 7 8 9 
2 3 4 5 14 9 8 
3 -1 5 6 7 14 9 
4 -1 6 13 8 9 10 
5 -1 7 -1 13 12 11 
6 -1 8 9 10 11 12 
7 -1 -1 -1 -1 -1 13 
8 9 10 11 12 13 14

목적지에 도달하자마자 도달하기까지 걸린 시간을 출력한다.

 

벽을 부순경우를 잘 보면 벽을 하나만 부순다고 했음에도 불구하고 많은 벽을 부순 흔적을 볼 수 있다.

(벽 위치에 숫자(시간)가 적혀져 있음)

 

"올바르지 않은 벽을 부쉈음에도"  //  "올바른 벽을 부쉈을 경우 목적지에 도달"한 시간이 더 빠르기에

올바르지 않은 벽을 부수는 경우를 무시할 수 있는 것이다.

 

이것이 이 문제의 핵심 포인트인 것 같다.