문제

BOJ 16973: 직사각형 탈출 https://www.acmicpc.net/problem/16973

풀이

조건

• 격자판의 각 칸에는 빈 칸 또는 벽이 있다.
• 직사각형은 벽이 있는 칸에 있을 수 없다.
• 직사각형은 격자판을 벗어날 수 없다.
• 직사각형은 한 번에 왼쪽, 오른쪽, 위, 아래 중 한 방향으로 한 칸 이동시킬 수 있다.
• 직사각형의 가장 왼쪽 위칸은 (Sr, Sc)에 있을 때, 이 직사각형의 가장 왼쪽 위칸을 (Fr, Fc)로 이동시키기 위한 최소 이동 횟수를 구한다.
• 최소 이동 횟수를 출력한다. 이동할 수 없는 경우에는 -1을 출력한다.

풀이 순서

• 벽 위치의 값을 -1로 바꾼다.
  • BFS로 거리의 최솟값을 구할 때 헷갈리지 않기 위해 바꾼다.
• 벽 위치를 List에 미리 넣어둔다.
• BFS 사용하여 최소 이동 횟수를 찾는다.
  • Queue에서 위치값을 뽑아낸다.
  • 뽑아낸 위치가 목표 위치에 도달하면 해당 위치에 적힌 값을 구하고 탐색을 종료한다.
  • 해당 위치에서 4방향을 탐색한다.
  • 탐색한 위치의 범위와 방문 여부를 체크한다.
  • 탐색한 위치에서의 사각형의 범위와 벽이 있는지 체크한다.
    • 사각형의 범위를 모두 체크하면 시간 초과에 걸린다.
    • List에서 벽의 위치를 차례로 꺼내서 벽의 위치가 사각형 범위 안에 있는지 체크한다.
  • 탐색한 위치로 이동이 가능하면 Queue에 넣고 방문체크를 한 뒤 새로운 거리값을 삽입한다.

코드

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

public class Main {  
	
	static int N, M;
	static int h, w, sx, sy, fx, fy;
	static int[][] map;
	
	static List<Pos> list;
	
	static int[] dx = {0, 0, 1, -1};
	static int[] dy = {1, -1, 0, 0};
	
	static int ans;

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		list = new ArrayList<>(); // 벽 위치 넣을 리스트
		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] = Integer.parseInt(st.nextToken());
				if(map[i][j] == 1) {
					map[i][j] = -1; // 벽 위치의 값을 -1로 교체
					list.add(new Pos(i, j)); // 벽 위치를 리스트에 넣음
				}
			}
		}
		
		st = new StringTokenizer(br.readLine(), " ");
		h = Integer.parseInt(st.nextToken()); // 사각형 가로 길이
		w = Integer.parseInt(st.nextToken()); // 사각형 세로 길이
		sx = Integer.parseInt(st.nextToken()); // 시작 위치
		sy= Integer.parseInt(st.nextToken()); // 시작 위치
		fx = Integer.parseInt(st.nextToken()); // 목표 위치
		fy = Integer.parseInt(st.nextToken()); // 목표 위치
		
		ans = -1; // 답 ( 최소 거리 )
		bfs();
		System.out.println(ans);
	}
	
	static void bfs() {
		Queue<Pos> que = new LinkedList<>();
		boolean[][] isChecked = new boolean[N+1][M+1];
		
		que.add(new Pos(sx, sy));
		isChecked[sx][sy] = true;
		
		while(!que.isEmpty()) {
			Pos p = que.poll();
			
			int curX = p.x;
			int curY = p.y;
			
			// 목표 위치에 도달하면 탐색 종료
			if(curX == fx && curY == fy) {
				ans = map[curX][curY];
				return;
			}
			
			for(int t=0; t<4; t++) {
				int nx = curX + dx[t];
				int ny = curY + dy[t];
				
				// 탐색한 위치의 범위와 방문 여부 체크
				if(nx < 1 || ny < 1 || nx > N || ny > M || isChecked[nx][ny]) continue;				
				// 해당 사각형의 범위와 벽이 있는지 체크
				if(!isPossible(nx, ny)) continue;
				
				// 이동 가능한 위치면 Queue에 넣고 방문 체크, 거리값 삽입
				if(map[nx][ny] == 0) {
					que.add(new Pos(nx, ny));
					isChecked[nx][ny] = true;
					map[nx][ny] = map[curX][curY] + 1;
				}
			}

		}
		
	}
	
	// 사각형이 있을 수 있는지 체크하는 메소드
	static boolean isPossible(int x, int y) {
		// 사각형이 범위를 벗어나면 false 반환
		if(x+h-1 > N || y+w-1 > M) return false;
		// 벽의 위치를 차례로 꺼내서 범위 체크
		for(int i=0; i<list.size(); i++) {
			Pos p = list.get(i);
			
			int px = p.x;
			int py = p.y;
			
			if(px >= x && px <= x+h-1 && py >= y && py <= y+w-1) {
				return false;
			}
		}
		
		/*
		 * 아래의 부분이 시간초과가 되도록 한다.
		 * 매번 사각형이 범위 안에 있거나 사각형 안에 벽이 있는지 체크한다.
		 */
//		for(int i=x; i<x+h; i++) {
//			for(int j=y; j<y+w; j++) {
//				if(i > N || i < 1 || j > M || j < 1 || map[i][j] == -1) {
//					return false;
//				}
//			}
//		}
		
		return true;
	}
	
	static class Pos {
		int x, y;
		
		Pos(int x, int y){
			this.x = x;
			this.y = y;
		}
	}
}  

정리

• 사각형의 범위 안을 매번 조사하면 시간초과가 나서 다른 방법으로 개선하여 해결했다.