벽 부수고 이동하기[백준 2206][골드4][Java]

 

[광고 누르면 오늘의 행운 상승!!]

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

2206번: 벽 부수고 이동하기

단순히 BFS를 돌리면 벽을 뚫고 지나간 아이의 visit 배열이 남아있어서 벽을 뚫지 않은 아이가

지나가지 못한다. 그래서 3차원 배열로 벽을 뚫었을 때, 아직 뚫지 않았을 때 의 조건을 주어

BFS를 돌렸다. 

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

class Pos{
	int row, col, dis;
	int wall;
	public Pos(int row, int col, int dis ,int wall) {
		this.row = row;
		this.col = col;
		this.wall = wall;
		this.dis = dis;
	}
	
}
public class Main {
	public static int[] dx = {-1,0,1,0};
	public static int[] dy = {0,1,0,-1};
	public static int map[][];
	public static boolean visit[][][];
	public static int N,M;
	public static int ans=-1;
	public static Queue<Pos> q;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		visit = new boolean[2][N][M];
		map = new int[N][M];
		
		for (int i = 0; i < N; i++) {
			char[] ch = br.readLine().toCharArray();
			for (int j = 0; j < M; j++) {
				map[i][j] = ch[j] - '0';
			}
		}
		
		q = new LinkedList<>();
		
		q.add(new Pos(0,0,1,0));
		visit[0][0][0] = true;
		
		bfs();
		
		System.out.println(ans);
	}
	public static void bfs() {
		
		while(!q.isEmpty()) {
			Pos p = q.poll();
			
			if(p.row == N-1 && p.col == M-1) {
				ans = p.dis;
				return;
			}
			for (int i = 0; i < 4; i++) {
				int nx = p.row + dx[i];
				int ny = p.col + dy[i];
				
				if(nx < 0 || nx >= N || ny < 0 || ny >= M ) {
					continue;
				}
				//방문했으면
				if(visit[p.wall][nx][ny]) continue;
				//벽이 아님
				if(map[nx][ny] == 0) {
					q.add(new Pos(nx,ny,p.dis+1,p.wall));
					visit[p.wall][nx][ny]= true;
				}
				//벽
				if(p.wall == 0 && map[nx][ny] == 1) {
					q.add(new Pos(nx,ny,p.dis+1,1)); 
					visit[1][nx][ny]= true;
				}
			}
		}
	}
}