[BJ] 16973. 직사각형 탈출

www.acmicpc.net/problem/16973

16973번: 직사각형 탈출

 

✔ 문제 조건

1. 격자판의 가장 위쪽 위칸은 (1, 1), 가장 오른쪽 아래 칸은 (N, M).

1-1. 격자판의 각 칸은 빈 칸 or 벽

2. 이동시킬 직사각형의 가장 위쪽 위칸은 (sr, sc)이며, 크기는 W * H이다.

2-1. 직사각형은 벽이 있는 칸에 갈 수 있다.

3. 직사각형의 가장 위쪽 위칸은 (sr, sc)에서 시작해서 (er, ec)까지 갈 수 있는 최소 이동 횟수를 출력한다.

3-1. 출력할 수 없는 경우 -1을 출력한다.

 

✔ 접근 과정

1. 시작점 (sr, sc)을 방문 후 BFS를 시작한다.

2. 큐에서 꺼낸 위치에서 4방 탐색을 한다.

3. 4방 탐색을 시작할 위치 (nr, nc)를 직사각형의 가장 위쪽 위칸으로 생각한다.
(nr, nc)를 기준으로 직사각형의 네 꼭지점이 모두 격자판 범위 안에 있는지 확인한다.

4. 네 꼭지점이 모두 격자판 범위 안에 있다면, 새롭게 이동할 면적에 벽이 있는지 확인한다.

4-1. 상으로 움직인다면-> (nr, nc) 기준 직사각형의 윗줄만 살펴본다.

      하로 움직인다면  ->  (nr, nc) 기준 직사각형의 아랫줄만 살펴본다. 
      자로 움직인다면  ->  (nr, nc) 기준 직사각형의 왼쪽 줄만 살펴본다.
     우로 움직인다면   ->  (nr, nc) 기준 직사각형의 오른쪽 줄만 살펴본다.

5. 4에서 벽을 발견하지 못한다면 방문 체크를 한 후 큐에 넣어 방문한다.

6. 큐에서 꺼낸 위치가 도착 지점이라면 거리를 출력한다.

6-1. 도착 지점에 도달하지 못하고 큐가 비워졌다면 -1를 출력한다.

 

✔ 주의할 점

1. (nr, nc)를 기준으로 새 직사각형이 만들어질 때

(nr, nc)를 시작으로 한, H*W 넓이 만큼의 모든 직사각형 칸들을 탐색할 필요가 없다. (실제로 해보니 시간 초과가 났다.)

직사각형은 상하좌우로 한칸 씩만 움직이기 때문에, 움직이는 방향의 줄들에만 벽이 있는지 확인해보면 된다.

2. 접근 과정 4에서, 새롭게 이동할 면적의 위치는, 큐에서 꺼낸 위치 (cur) 기준이 아니라 (nr, nc) 기준으로 살펴보아야 한다. (nr, nc) 기준으로 직사각형이 놓아질 수 있는지 확인하고 갈 수 있으면 큐에 넣도록 설계했기 때문이다.

 

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

public class Main_BJ_16973_직사각형탈출 {
	static int N, M, H, W;
	static int[][] map;
	static int sr, sc, er, ec;
	static int[] dr = {-1, 1, 0, 0};
	static int[] dc = {0,  0, -1, 1}; // 상 하 좌 우
	
	public static void main(String[] args) throws Exception {
//		System.setIn(new FileInputStream("res/input_BJ_16973_직사각형탈출.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		
		N = stoi(st.nextToken());
		M = stoi(st.nextToken());
		
		map = new int[N+1][M+1];
		
		for(int i=1; i<=N; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for(int j=1; j<=M; j++) {
				map[i][j] = stoi(st.nextToken());
			}
		} 
		
		st = new StringTokenizer(br.readLine(), " ");
		
		H = stoi(st.nextToken());
		W = stoi(st.nextToken());
		
		sr = stoi(st.nextToken());
		sc = stoi(st.nextToken());
		er = stoi(st.nextToken());
		ec = stoi(st.nextToken());
	
		System.out.println(bfs(new Pos(sr, sc, 0)));
		
		br.close();
	}
	
	static int bfs(Pos start) {
		// 시작점 방문
		Queue<Pos> q = new ArrayDeque<>();
		boolean[][] v = new boolean[N+1][M+1];
		
		q.offer(start);
		v[start.r][start.c] = true;
		
		Pos cur;
		int nr, nc, nnr, nnc;
		boolean flag = true;
		
		while(!q.isEmpty()) {
			cur = q.poll();
			
			if(cur.r==er && cur.c==ec)
				return cur.dist;
			
			// 4방 탐색
			for(int d=0; d<4; d++) {
				nr = cur.r + dr[d];
				nc = cur.c + dc[d];
				
				// 정사각형의 네 꼭지점 범위 탐색 
				if(nr<1 || nr>N || nc<1 || nc>M || v[nr][nc] || 
						nr+H-1>N || nc+W-1>M ) continue;
				
				// 이동할 위치에 벽이 있는지 검사
				flag = true;
				if(d==0) { // 상
					nnr = nr;
					for(int i=0; i<W; i++) {
						nnc = nc + i;
						if(map[nnr][nnc]==1) {
							flag=false;
							break;
						}
					}
					
				} else if(d==1) { // 하
					nnr = nr +H-1;
					for(int i=0; i<W; i++) {
						nnc = nc + i;
						if(map[nnr][nnc]==1) {
							flag=false;
							break;
						}
					}

				} else if(d==2) { // 좌
					nnc = nc;
					for(int i=0; i<H; i++) {
						nnr = nr + i;
						if(map[nnr][nnc]==1) {
							flag=false;
							break;
						}
					}
					
				} else if(d==3) { // 우
					nnc = nc+W-1;
					for(int i=0; i<H; i++) {
						nnr = nr + i;
						if(map[nnr][nnc]==1) {
							flag=false;
							break;
						}
					}
					
				}
				
				if(flag) {
					q.offer(new Pos(nr, nc, cur.dist+1));
					v[nr][nc] = true;
				}

			} // for

		}

		return -1;
	}

	static class Pos {
		int r, c, dist;

		public Pos(int r, int c, int dist) {
			this.r = r;
			this.c = c;
			this.dist = dist;
		}
	}

	static int stoi(String str) {
		return Integer.parseInt(str);
	}
}