[Java] BOJ16973, 백준 - 직사각형 탈출

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

16973번: 직사각형 탈출

 

문제 자체는 그냥 BFS로 풀면 되는 문제이다.

다만 까다로운 조건이 두 가지 있음

 

1. 한 점이 아니라, 좌표 네 개짜리 네모로 BFS를 해야한다.

    > 처음에는 네 좌표를 int[4][2] 배열에 저장해서 비교할까 생각했었는데, 생각해보니 왼쪽 위와 오른쪽 아래,

       대각선 좌표끼리만 비교를 하면 나머지 두 좌표는 비교할 필요가 없다.

       그리고 가로 길이와 세로 길이가 주어지니까, 왼쪽 위의 좌표만 저장해놓으면 각각 가로 길이와 세로 길이를

       더해서 오른쪽 아래 좌표도 구할 수 있음.

       즉, 왼쪽 위의 좌표 하나만 저장해놓으면 된다!

 

좌표는 i ~ i+h-1  /  j ~ j+w-1

 

 

 

2. 네모 영역 중 한 군데라도 벽인 곳이 있으면 이동할 수 없다.

   > 이 조건을 해결하기 조금 까다로웠다.

이 문제는 두 가지 코드로 해결할 수가 있다.

 

(1) 네모의 가장자리 부분만 검사

 - 어차피 cnt 1당 한 칸씩만 이동할 수 있기 때문에, 차이나는부분은 이동 방향에 따라서 네 가장자리 중 한 부분일 것이다.

하지만 어떤 방향으로 일일이 비교하는게 더 힘들기때문에 이동할때마다 네 가장자리를 모두 비교해준다!

아래의 경우 주황색 부분만 검사하면 된다.

// 인덱스가 유효하다면
// 새로 생기는 행/열에 벽이 있는지 확인해야함
for (int idx = ni; idx < ni + h; idx++) {
	if (map[idx][nj] == 1 || map[idx][nj + w - 1] == 1)
		continue dir;
	}
for (int idx = nj; idx < nj + w; idx++) {
	if (map[ni][idx] == 1 || map[ni + h - 1][idx] == 1)
		continue dir;
}

인덱스에 대한 부분들은 스스로 고민해보는게 좋을 듯!

 

요 두 가지 사항을 제외하고는 BFS에 익숙하다면 쉽게 풀 수 있는 문제인듯

 

*처음에 시간초과 났던 이유

BFS에서  visited 배열을 체크할 때,

큐에서 뺄 때 말고 넣을 때 체크를 해야 함!!!

뺄 때 체크를 하면 중복으로 큐에 담길 수가 있다.

이것 때문에 한시간 디버깅했으니 다음부턴 꼭 주의하자 😂

+ 반복문 라벨 사용 최소화하고 차라리 함수로 빼기

 

<전체 소스코드>

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

//https://www.acmicpc.net/problem/16973
public class Main {

	private static int[][] move = { { 1, 0 }, { 0, 1 }, { -1, 0 }, { 0, -1 } };
	private static int n, m, h, w, fr, fc, cnt;
	private static int[][] map;
	private static boolean[][] visited;
	private static Queue<Point> 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());
		map = new int[n + 1][m + 1];
		visited = new boolean[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());
		}

		st = new StringTokenizer(br.readLine());
		h = Integer.parseInt(st.nextToken());
		w = Integer.parseInt(st.nextToken());

		q = new LinkedList<>();
		int sr = Integer.parseInt(st.nextToken());
		int sc = Integer.parseInt(st.nextToken());
		q.add(new Point(sr, sc));
		visited[sr][sc] = true;

		fr = Integer.parseInt(st.nextToken());
		fc = Integer.parseInt(st.nextToken());
		// end Input

		if (bfs())
			System.out.println(cnt);
		else
			System.out.println("-1");

	}

	private static boolean bfs() {
		while (!q.isEmpty()) {
			int size = q.size();
			for (int s = 0; s < size; s++) {
				Point p = q.poll();

				if (p.i == fr && p.j == fc)
					return true;

				dir: for (int i = 0; i < 4; i++) { // 방향 탐색
					int ni = p.i + move[i][0];
					int nj = p.j + move[i][1];

					// 인덱스 검사
					if (ni <= 0 || ni > n || nj <= 0 || nj > m || visited[ni][nj])
						continue;
					if (ni + h - 1 > n || nj + w - 1 > m)
						continue;

					// 인덱스가 유효하다면
					// 새로 생기는 행/열에 벽이 있는지 확인해야함
					for (int idx = ni; idx < ni + h; idx++) {
						if (map[idx][nj] == 1 || map[idx][nj + w - 1] == 1)
							continue dir;
					}
					for (int idx = nj; idx < nj + w; idx++) {
						if (map[ni][idx] == 1 || map[ni + h - 1][idx] == 1)
							continue dir;
					}

					// 해당 방향으로 이동 가능한 경우 : 큐에 담음
					q.add(new Point(ni, nj));
					visited[ni][nj] = true;
				}
			}
			cnt++;
		} // end BFS
		return false;
	}
}

class Point {
	int i, j;

	Point(int i, int j) {
		this.i = i;
		this.j = j;
	}
}