자바(백준) 16973 직사각형 탈출

오답 노트 & 새로 알게 된 점

풀이는 BFS를 이용하여 최소 경로를 구했다.

 

가장 왼쪽 위 칸부터 가장 오른쪽 아래 칸까지 범위를 모두 탐색하면서 1이 있는지 없는지 판단했다.

 

처음에는 bfs를 아래와 같이 짰다.

 

for (int i = 0; i < 4; i++) {
                int X = info.x + dx[i];
                int Y = info.y + dy[i];

                if(!isRangeTrue(X, Y)) continue;
                if(visit[X][Y]) continue;

                q.offer(new Info(X, Y, info.cnt + 1));
                visit[X][Y] = true;
            }

 

static boolean isRangeTrue(int x, int y) {
        int X = x + hei - 1;
        int Y = y + wid - 1;
        if(x < 1 || x > row || y < 1 || y > col || X > row || Y > col) return false;

        for (int i = x; i <= X; i++) {
            for (int j = y; j <= Y; j++) {
                if(A[i][j] == 1) return false;
            }
        }

        return true;
    }

하지만 이렇게 되면 움직일 때마다 모든 X, Y를 이중 포문 돌리기 때문에 TLE가 난다(내 생각)

 

따라서 bfs에서 미리 걸러주는 것이 좋다.

1. X,Y의 범위가 격자판을 넘어가는지

2. 가장 왼쪽 위 칸이 옮길 수 있는지

2-1) 옮길 수 있다면 isRangeTrue를 호출하여 검사하는 것이다.

 

---

코드

import java.io.*;
import java.util.*;
 
public class Main {
    static int atoi(String str) {
        return Integer.parseInt(str);
    }
    static int row, col, hei, wid;
    static int A[][];
    static Info start = null, end = null;
    static int dx[] = {0, 0, 1, -1};
    static int dy[] = {1, -1, 0, 0};
    static boolean visit[][];
    static int ans = -1;
    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws IOException {
        input();
        pro();
    }
 
    static void pro() {
        bfs();
 
        if(sb.length() == 0) sb.append(-1);
 
        System.out.println(sb);
    }
 
    static void bfs() {
        Queue<Info> q = new ArrayDeque<>();
        q.offer(start);
        visit[start.x][start.y] = true;
 
        while (!q.isEmpty()) {
            Info info = q.poll();
 
            if(info.x == end.x && info.y == end.y){
                sb.append(info.cnt);
                return;
            }
 
            for (int i = 0; i < 4; i++) {
                int X = info.x + dx[i];
                int Y = info.y + dy[i];
 
                if(X < 1 || X > row || Y < 1 || Y > col) continue;
 
                if(!visit[X][Y] && A[X][Y] == 0){
                    if(!isRangeTrue(X, Y)) continue;
 
                    q.offer(new Info(X, Y, info.cnt + 1));
                    visit[X][Y] = true;
                }
            }
        }
    }
 
 
 
    static boolean isRangeTrue(int x, int y) {
        int X = x + hei - 1;
        int Y = y + wid - 1;
        if(X > row || Y > col) return false;
 
        for (int i = x; i <= X; i++) {
            for (int j = y; j <= Y; j++) {
                if(A[i][j] == 1) return false;
            }
        }
 
        return true;
    }
 
    static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        row = atoi(st.nextToken());
        col = atoi(st.nextToken());
 
        A = new int[row + 1][col + 1];
        visit = new boolean[row + 1][col + 1];
 
        for (int i = 1; i <= row; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= col; j++) {
                A[i][j] = atoi(st.nextToken());
            }
        }
 
        st = new StringTokenizer(br.readLine());
 
        hei = atoi(st.nextToken());
        wid = atoi(st.nextToken());
        start = new Info(atoi(st.nextToken()), atoi(st.nextToken()), 0);
        end = new Info(atoi(st.nextToken()), atoi(st.nextToken()), 0);
    }
 
    static class Info{
        int x, y, cnt;
 
        public Info(int x, int y, int cnt) {
            this.x = x;
            this.y = y;
            this.cnt = cnt;
        }
    }
}