백준 2206번 JAVA

1. 문제

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

2. 소스코드

import java.io.*;
import java.util.*;

public class a2206 {
	static int n,m;
	static int arr[][];
	static boolean visit[][][];

	static int dx[]= {1,-1,0,0};
	static int dy[]= {0,0,1,-1};
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=new StringTokenizer(br.readLine());
		n=Integer.parseInt(st.nextToken()); // 세로
		m=Integer.parseInt(st.nextToken()); // 가로
		arr=new int[n][m];
		visit=new boolean[n][m][2];
		
		for(int i=0;i<n;i++) {
			String s=br.readLine();
			for(int j=0;j<m;j++) {
				arr[i][j]=s.charAt(j)-'0';
			}
		}
		
		System.out.print(bfs());
		
	}
	
	public static int bfs() {
		Queue<int []> q=new LinkedList<>();
		q.add(new int[] {0,0,0,1});
		visit[0][0][0]=true;
		
		while(!q.isEmpty()) {
			int cury=q.peek()[0]; 
			int curx=q.peek()[1];
			int wall=q.peek()[2];
			int dist=q.peek()[3];
			q.poll();
			
			if(cury==n-1 && curx==m-1) {
				return dist;
			}
			
			for(int i=0;i<4;i++) {
				int py=cury+dy[i];
				int px=curx+dx[i];
				
				if(py>=0 && py<n && px>=0 && px<m) {
					// 갈 수 있고 아직 방문하지 않은 경우
					if(arr[py][px]==0 && !visit[py][px][wall]) {
						q.add(new int[] {py,px,wall,dist+1});
						visit[py][px][wall]=true;
					} 
					// 갈 수 없고 아직 벽 안 부쉈고 방문한적 없는 경우
					else if(arr[py][px]==1 && wall==0 && !visit[py][px][1]) {
						q.add(new int[] {py,px,1,dist+1});
						visit[py][px][1]=true;
					}
				}		
			}
		}
		return -1;
	}
}

3. 풀이 방법

• 벽을 부순 상태인지 아닌지를 저장해줘야 함
  따라서 boolean visit 3차원 배열을 선언 [n][m][2];
  wall=0 : 벽을 부수지 않았을 때
  wall=1 : 벽을 부쉈을 때

1. 갈 수 있고 방문하지 않은 경우
2. 갈 수 없고 벽을 부수지 않았고 방문하지 않은 경우

이 두가지의 경우로 나눠서 풀어야 함

• 첫번째의 경우, 벽을 부수지 않아도 되기 때문에 현재 wall 값=0 을 그대로 사용
  두번째의 경우, 벽을 부숴야 하기 때문에 wall=1 값을 사용

• 현재 위치가 도착지점이라면 최단 거리를 리턴
  큐를 빠져나갔는데도 도착지점이 아니라면 -1 리턴