[백준,BOJ 2206] 벽 부수고 이동하기(JAVA 구현,추가풀이)

-내 생각

  너무 어렵다... 이전까지 문제들을 풀어보면서 너무 자만했나 보다. 문제 자체는 이해가 가는데 구현을 못하겠다 ㅠㅠ

티스토리 규글님 블로그의 코드를 참고했는데, 솔직히 이해 안 가는 부분이 있어서 반복해서 봐야 할 것 같다...

https://kim6394.tistory.com/201

[백준 2206] 벽 부수고 이동하기 (Java, BFS)

 

import java.util.*;
class xy{
	int x;
	int y;
	int z;
	int dis;
	public xy(int x,int y,int dis,int z) {
		this.x = x;
		this.y = y;
		this.z = z;
		this.dis = dis;
	}
}
public class Main {
	static int node [][];
	static int check[][];
	static int n,m,ans;
	static int dy[] = {1,-1,0,0};
	static int dx[] = {0,0,1,-1};
	public static void bfs(int a,int b) {
		Queue<xy> queue = new LinkedList();
		
		queue.offer(new xy(a,b,1,0));
			
		check[a][b] =0;
		while(!queue.isEmpty()) {
			xy q = queue.poll();
			
			if(q.x==n-1 && q.y==m-1) {
				ans = q.dis;
				break;
			}
			
			
			
			for(int i=0;i<4;i++) {
				int x =q.x + dx[i];
				int y = q.y + dy[i];
				
				if(x<0 || y<0|| x>=n ||y>=m)continue;
				////////////////이해 안가는부분 ㅠㅠ /////////////
				if(check[x][y]<=q.z) continue;
				
				
				if(node[x][y]==0) {
					check[x][y] = q.z;
					queue.offer(new xy(x,y,q.dis+1,q.z));
				}
				else {
					if(q.z==0) {
						check[x][y]=q.z+1;
						queue.offer(new xy(x,y,q.dis+1,q.z+1));
					}
				}
                ////////////////////////////////////////////////
			}
		}
	
	}
	


	
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);	
		
		n = sc.nextInt();
		 m = sc.nextInt();
		
		node = new int[n][m];
		check = new int[n][m];
		
		for(int i=0;i<n;i++) {
			String row = sc.next();
			for(int j=0;j<m;j++) {
				node[i][j] = row.charAt(j)-'0';
				Arrays.fill(check[i], Integer.MAX_VALUE);
			}
		}
		node[0][0]=node[n-1][m-1] =0;
		
		
		ans = Integer.MAX_VALUE;
		
		bfs(0,0);
		
		for(int i=0;i<n;i++) {
			
			for(int j=0;j<m;j++) {
				System.out.print(check[i][j]+" ");
			}
			System.out.println();
		}
		if(ans == Integer.MAX_VALUE) {
			System.out.println("-1");
		}else {
			System.out.println(ans);
		}

		
		
//		
		
	}
	
}

---

  DFS, BFS의 단계별 풀어보기 마지막 문제이다. 저번의 풀이와 마찬가지로 푸는데 어려움이 있었다. check배열을 통해 방문 체크를 하지 않을 경우 메모리 초과 문제가 발생하고, 방문 체크를 할 때는 반례에 걸려서 오답처리가 났다.

 

  그 이유는 벽을 한 번뚫어서 특정 좌표에 도착하는 경로의 수와 뚫지 않고 왔을 때의 경로의 수가 같을 때, 큐에 벽을 뚫고 온 좌표가 먼저 BFS 탐색을 수행해 다음 좌표들의 경로의 수가 벽을 뚫고 온 경우로 저장되기 때문에 벽을 쓸데없이 뚫고 오는 경우가 발생한 것이다. 이를 해결하기 위해 고민해봤지만, 짧은 지식으로는 어쩔 수 없어 검색을 통해 알아보았는데, 대다수의 사람들이 3차원 배열을 이용해 두 가지 경우를 분리해서 방문 체크를 한다는 것을 알고 한 번 해보았더니 제대로 나오더라... 아래가 그 코드이다.

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

class Dot{ // 좌표 저장 클래스
	int x;
	int y;
	int cnt;
	public Dot(int x,int y,int cnt) {
		this.x = x;
		this.y = y;
		this.cnt = cnt;
	}
}

class Main {
		
	static int[] dx = {1,-1,0,0};
	static int[] dy = {0,0,1,-1};
	static int n,m; // 정적변수로 선언 할 필요 없다. 여러 가지 풀이를 시도하던 과정에서 남았다.
	
    // BFS 메소드
	static void bfs(int[][] a,int[][][] check,Dot d) {
		Queue<Dot> q = new LinkedList<>();
		
		q.offer(d);
		check[0][d.x][d.y] = 1; // 벽울 뚫지 않은 경우의 체크 배열 시작지점
		check[1][d.x][d.y] = 1; // 벽을 뚫을 경우의 체크 배열 시작지점
        
		while(!q.isEmpty()) {
			Dot d_p = q.poll();
			int x = d_p.x;
			int y = d_p.y;
			
            // 상하좌우 탐색
			for(int i=0;i<4;i++) {
				int nx = x + dx[i];
				int ny = y + dy[i];
				
                // 좌표 벗어나는 경우 걸러내기
				if(nx <0 || nx >= a.length || ny <0 || ny >= a[nx].length) continue;
				
                // 벽을 뚫고 오지 않았다면,
				if(d_p.cnt == 0) {
                	// 벽을 뚫지 않은 경우의 체크 배열을 방문하지 않고 벽이 없는 길은
					if(check[d_p.cnt][nx][ny] == Integer.MAX_VALUE && a[nx][ny] == 0) {
						
                        // 그대로 벽을 뚫지 않은 경우의 체크 배열을 증가시킨다.
						check[d_p.cnt][nx][ny] = check[d_p.cnt][x][y] + 1;
						
                        // 이후 큐에 삽입.
						q.offer(new Dot(nx,ny,d_p.cnt));
					}	
					
                    // 벽이 있는 길은 벽을 뚫고 온 경우의 체크 배열을 방문 여부를 체크
					if(check[1][nx][ny] == Integer.MAX_VALUE && a[nx][ny] == 1) {
                    	// 처음 벽을 뚫으므로 벽이 없는 경우의 체크 배열의 값+1을 벽을 뚫은 경우의 체크 배열에 저장
						check[1][nx][ny] = check[d_p.cnt][x][y] + 1;
						
                        // 이후 큐에 삽입.
						q.offer(new Dot(nx,ny,1));
					}
				}else { // 벽을 한 번 뚫은 경우는
					
                    // 벽을 뚫고 온 경우의 체크배열에서 방문하지 않고 벽이 없는 길인 경우
					if(check[d_p.cnt][nx][ny] == Integer.MAX_VALUE && a[nx][ny] == 0) {
						
                        // 체크배열 값 증가
						check[d_p.cnt][nx][ny] = check[d_p.cnt][x][y] + 1;
						
                        // 이후 큐에 삽입.
						q.offer(new Dot(nx,ny,d_p.cnt));
					}					
                    // 벽을 이미 한 번 뚫고 온 경우이기 때문에 벽이 있는 길은 고려할 필요가 없다.
				}				
			}
		}
	}
	
	public static void main(String[] args)  {
		Scanner in = new Scanner(System.in);
		
		n = in.nextInt();
		m = in.nextInt();
		
		int a[][]= new int[n][m];
		int check[][][] = new int[2][n][m];
		
        // 벽 데이터 입력
		for(int i =0;i<a.length;i++) {
			String str = in.next();
			for(int j=0;j<a[i].length;j++) {
				a[i][j] = str.charAt(j)-'0';				
			}
		}
        
        // 이건 방문 여부 체크를 위해 초기화부분. 각자 방식으로 바꾸어도 무관
		for(int j=0;j<2;j++) {
          for(int i =0;i<check[j].length;i++) {
              Arrays.fill(check[j][i],Integer.MAX_VALUE);
          }
       	}
		
		// BFS 호출
		bfs(a,check,new Dot(0,0,0));
		
        // 두 가지의 체크 배열의 마지막 좌표에 경로의 수가 저장되므로
        // 두 가지 중 가장 작은 값을 찾았을 때 초기화 된 값이 그대로 있는 경우는
		if(Math.min(check[0][n-1][m-1], check[1][n-1][m-1]) == Integer.MAX_VALUE)
			System.out.println(-1); // 경로가 존재할 수 없다.
		else // 이외에는
        	// 두 가지 중 가장 작은 값을 출력하면 최소 경로가 된다. 
			System.out.println(Math.min(check[0][n-1][m-1], check[1][n-1][m-1]));
		
	}
}

 

  참고로 필자가 걸린 반례는 아래이다.

6 4
0000
1110
1000
0000
0111
0100

 

어려워!