백준 2206 벽 부수고 이동하기(JAVA)

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

2206번: 벽 부수고 이동하기

 

문제 풀이

먼저 나는 이 문제를 보고 BFS방식에서 큐에 벽을 부쉈는지 확인해주는 변수를 넣어주면 되는 문제인 줄 알았다.

하지만 틀렸다.

여기서 내가 생각하지 못했던 것이 벽을 부수고 진행했던 경로와 벽을 부수지 않고 진행한 경로가 겹칠 수 있는 구간이 있을 수 있다는 것을 놓쳤었다.

그렇기에 이 문제를 해결하기 위해선 평소에 쓰던 visted 변수를 2개를 만들어서 벽을 부수고 간 경로의 visited와 벽 부수지 않은 경로의 visited를 나누어서 해야한다.

 

전체 코드

import java.io.*;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {	
	static int n;
	static int m;
	static int[][] map;
	static boolean[][][] visied;
	static int[] nextx = {1,-1,0,0};
	static int[] nexty = {0,0,1,-1};
	static int distance;
	static int BFS() {
		Queue<int[]> queue = new LinkedList<>();
		queue.add(new int[] {0,0,1,1});
		boolean isCheck = false;
		while(!queue.isEmpty()) {
			int[]now = queue.poll();
			int now_x = now[0];
			int now_y = now[1];
			int count = now[2];
			int onecount = now[3];
			if(now_x == n-1 && now_y == m-1) {
				distance = count;
				isCheck = true;
				break;
			}
			if(onecount == 0) {
				for(int i =0; i<4;i++) {
					int next_x = now_x + nextx[i];
					int next_y = now_y + nexty[i];
					if(next_x<0|| next_y<0 || next_x>=n|| next_y>=m) {
						continue;
					}
					if(map[next_x][next_y] == 1) continue;
					if(visied[next_x][next_y][1]) continue;
					
					queue.add(new int[] {next_x,next_y,count+1, onecount});
					visied[next_x][next_y][1] = true;
					}
			}
			else {
				for (int i = 0; i < 4; i++) {
					int next_x = now_x + nextx[i];
					int next_y = now_y + nexty[i];
					if (next_x < 0 || next_y < 0 || next_x >= n || next_y >= m) {
						continue;
					}
					if (map[next_x][next_y] == 1) {
						if(visied[next_x][next_y][1]) continue;
						queue.add(new int[] { next_x, next_y, count + 1, onecount - 1 });
						visied[next_x][next_y][1] = true;

					}
					else{
						if(visied[next_x][next_y][0]) continue;
						queue.add(new int[] { next_x, next_y, count + 1, onecount });
						visied[next_x][next_y][0] = true;
						
					}
				}
			}
		}
			if(isCheck) return 1;
			else return 0;
		}
	
	
	public static void main(String[] args) throws NumberFormatException, 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());
		map = new int[n][m];
		visied = new boolean[n][m][2];
		for(int i =0; i<n;i++) {
			String s = br.readLine();
			for(int j =0; j<m;j++) {
				map[i][j] = Integer.parseInt(s.substring(j,j+1));
			}
		}
		
		if(BFS() == 0) System.out.print(-1);
		else System.out.print(distance);
	}
}