[BJ] 2206. 벽 부수고 이동하기

2206. 벽 부수고 이동하기

www.acmicpc.net/problem/2206

2206번: 벽 부수고 이동하기

 

오래 걸렸던 문제인데..

1. 벽이 있는 곳의 위치를 큐에 넣어서. 하나씩 뽑으며 그 부분의 벽을 부시고 매번 bfs를 돌리니 N<=10000, M<=10000이기 때문에 시간 초과가 난다.

2. 그래서 dist (거리) 배열을 3차원 배열로 만들어서, 벽을 부셨을 경우와 부시지 않았을 경우로 나눈다.
 - 벽을 한번 부셨다가, 더 이상 벽을 부수지 못해서 큐에 들어가지 못할 경우 해당 위치의 dist 배열은 이미 초기화가 되어 있다.
 - 이럴 경우 다음에 벽을 부실 때 dist 배열이 초기화 되어 있어 나아가지 못한다고 생각 했지만. 어차피 이미 전에 벽을 부셨을 때 보다 더 적은 칸수로 목적지까지 나아갈 수 없다.
 - 따라서 dist 배열을 행/열/2(벽을 부셨을 때/ 부시지 않았을 때) 로 크기를 지정해주면 된다.

+ 복습하며 update

1. 큐에서 위치값을 저장할 때는 위치 class를 만들어서 사용하자. 일차원 배열 인덱스로 r, c에 접근하는 것보다 덜 헷갈린다.

2. (nr, nc)까지의 이동값은 이전 위치(r, c)에서의 이동값 +1이며, dist값들과 visited 배열을 따로 관리할 필요 없이 visited 배열에 한꺼번에 관리한다.

 

import java.io.*;
import java.util.*;
// 210214

public class Main_BJ_2206_벽부수고이동하기 {
	static int N, M;
	static int[][] map;
	static int[][][] visited;
	static Queue<Pos> q;
	static int[] dr = {-1, 0, 1, 0};
	static int[] dc = {0, -1, 0, 1};
	
	static int stoi(String str) {
		return Integer.parseInt(str);
	}
	
	static class Pos {
		int r, c, flag; // flag 0 -> 벽 안부숨, 1 -> 벽 부숨

		public Pos(int r, int c, int flag) {
			this.r = r;
			this.c = c;
			this.flag = flag;
		}
	}
	
	static void bfs() {
		q.offer(new Pos(1, 1, 0)); // 시작점
		visited[1][1][0] = 1; // 시작점 거리 1
		
		while(!q.isEmpty()) {
			Pos p = q.poll();
			
			for(int d=0; d<4; d++) {
				int nr = p.r + dr[d];
				int nc = p.c + dc[d];
				
				if(nr<1 || nr>N || nc<1 || nc>M || visited[nr][nc][p.flag]>0) continue;
				
				// 벽x -> 방문
				if(map[nr][nc]==0 ) {
					visited[nr][nc][p.flag] = visited[p.r][p.c][p.flag] + 1;
					q.offer(new Pos(nr, nc, p.flag));
				}
				else { // 벽인데
					// 아직 벽을 부순 적으면 벽 부수고 이동
					if(p.flag==0) {
						visited[nr][nc][1] = visited[p.r][p.c][p.flag] + 1;
						q.offer(new Pos(nr, nc, 1));
					}
				}

			}

		}

	}
	
	static void check() {
		if(visited[N][M][0]==0 && visited[N][M][1]==0) {
			// 둘 다 방문 x
			System.out.println(-1);
		} else if(visited[N][M][0]==0) {
			System.out.println(visited[N][M][1]);
		} else if (visited[N][M][1]==0) {
			System.out.println(visited[N][M][0]);
		} else {
			System.out.println(Math.min(visited[N][M][0], visited[N][M][1]));
		}
	}
	
	public static void main(String[] args) throws Exception {
//		System.setIn(new FileInputStream("res/input_BJ_2206_벽부수고이동하기.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine().trim(), " ");
		 
		N = stoi(st.nextToken());
		M = stoi(st.nextToken());
		
		map = new int[N+1][M+1];
		visited = new int[N+1][M+1][2]; // 세번째 1 - 벽 부셨을 때, 0 - 안부셨을 때
		q = new ArrayDeque<>();
		
		String[] str;
		for(int i=1; i<=N; i++) {
			str = br.readLine().trim().split("");
			for(int j=1; j<=M; j++) {
				map[i][j] = stoi(str[j-1]);
			}
		}
		
		bfs();
		
		check();
		
		br.close();
	}
}