BOJ - 2206 ) 벽부수고 이동하기

---

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

2206번: 벽 부수고 이동하기

---

예전에 못풀어서 끙끙앓던 문제였는데 다시 생각해보니 쉬웠다. 큐에 들어가는 노드에 벽을 부수었는지?

 

만 체크하면 된다고 생각했었는데, 벽을 부수고 진행하는 경로가 벽을 부수지 않고 진행하는 경로를 방해하는

 

경우의 수가 생겼다. 따라서 벽을 부순경우에는 VISIT체크시 벽을 부순 경우끼리 체크를 해주어야한다.

 

벽을 부수고 진행하는 경로때문에 안부수고 갈수있는 경로에 방문체크가 되어있다면, 

 

목적지에 한칸 직전에 벽이 있으면 경로를 찾지못하는경우가생긴다.

 

이제 BFS/DFS 그만풀고 그래프이론과 DP문제를 파야겠다.

 

 

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		int map[][] = new int[n][m];
		int dir[][] = {{0,1},{1,0},{-1,0},{0,-1}};
		boolean visit[][][] = new boolean[n][m][2];
		
		for(int y = 0 ; y < n ; y++) {
			char[] temp = br.readLine().toCharArray();
			for(int x = 0 ; x< m ; x++) {
				map[y][x] = temp[x]-'0';
			}
		}
		ArrayDeque<int []> dq= new ArrayDeque<>();
		dq.push(new int[] {0,0,0,1});
		visit[0][0][0] = true;
		int ans = 987654321;
		while(!dq.isEmpty()) {
			
			int []now = dq.poll();
			if(now[0]==n-1 && now[1] ==m-1) {
				if(ans > now[3]) {
					ans = now[3];
				}
				break;
			}
			
			for(int index = 0 ; index < 4 ; index++) {
				
				int ny = now[0] + dir[index][0];
				int nx = now[1] + dir[index][1];
				if(ny >= 0 && nx >=0 && ny < n && nx <m) {
					
					if(!visit[ny][nx][now[2]]  && map[ny][nx] ==0) {
						visit[ny][nx][now[2]] = true;
						dq.add(new int[] {ny,nx,now[2],now[3]+1});
					}
					
					if(!visit[ny][nx][1] && map[ny][nx]==1 && now[2]==0) {
						visit[ny][nx][1] = true;
						dq.add(new int[] {ny,nx,1,now[3]+1});
					}
				}
			}
		}
		System.out.println((ans = ans == 987654321 ? -1 : ans));
		
	}

}

---