알고리즘 문제 풀이

백준 2206 벽 부수고 이동하기 (Java 자바)

superbono 2021. 3. 26. 19:57
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class bj2206_벽부수고이동하기 {
	static int map[][];
	static boolean visited[][][];
	static int N, M, res;
	static Queue <Data> q;
	
	// 상 하 좌 우
	static int dx[] = {-1, 1, 0, 0};
	static int dy[] = {0, 0, -1, 1};
	
	static class Data {
		int x;
		int y;
		int cnt;
		int chance; // 0:벽 뚫은 적 없음		 1: 있음
		
		public Data(int x, int y, int cnt, int chance) {
			super();
			this.x = x;
			this.y = y;
			this.cnt = cnt;
			this.chance = chance;
		}
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		N = sc.nextInt();
		M = sc.nextInt();
		map = new int [N + 1][M + 1];
		visited = new boolean [N + 1][M + 1][2];
		res = 2147000000;
		
		for(int i = 1; i <= N; i++) {
			String str = sc.next();;
			for(int j = 1; j <= M; j++) {
				map[i][j] =  str.charAt(j - 1) - '0';
			}
		}
		
		bfs();
		System.out.println(res == 2147000000? -1 : res);
	}
	
	static void bfs() {
		q = new LinkedList<>();
		q.offer(new Data(1, 1, 1, 0));
		visited[1][1][0] = true;
		
		Data cur = null;
		int nx, ny;
		while(!q.isEmpty()) {
			cur = q.poll();
			if(cur.x == N && cur.y == M) {
				if(res > cur.cnt)
					res = cur.cnt;
				return;
			}
			
			for(int dir = 0; dir < 4; dir++) {
				nx = cur.x + dx[dir];
				ny = cur.y + dy[dir];
				
				if(nx < 1 || ny < 1 || nx >= N + 1 || ny >= M  + 1 ) 
					continue;
				if(visited[nx][ny][cur.chance]) continue;
				
				if(map[nx][ny] == 1) {
					if(cur.chance == 0) {
						visited[nx][ny][1] = true;
						q.offer(new Data(nx, ny, cur.cnt + 1, 1));
					}
				}
				else {
					visited[nx][ny][cur.chance] = true;
					q.offer(new Data(nx, ny, cur.cnt + 1, cur.chance));
					
				}
			}
		}
	}
}

// 최적화 할 부분이 아직 많고... 통과는 되나 완벽하지 않은 코드다