[백준] 16973. 직사각형 탈출 - Java

🖇️ 문제 링크

16973번: 직사각형 탈출

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

 

---

💡 문제 분석

직사각형의 가장 왼쪽 위칸(Sr, Sc)를 기준으로 4방향으로 BFS를 진행합니다.

4방향을 탐색할 때, H * W 크기의 직사각형 중 한칸이라도 벽에 부딪힌다면 continue.

(Fr, Fc) 좌표를 찾아낸다면 종료합니다.

 

 

---

⌨️ 코드

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

public class Q16973 {

    static int N, M, H, W, sy, sx, fy, fx;
    static int[][] map, dist;
    static int[] dy = {-1, 0, 1, 0}, dx = {0, 1, 0, -1};

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();
        map = new int[N][M];
        dist = new int[N][M];
        for(int i = 0; i < N; i++)
            for(int j = 0; j < M; j++)
                map[i][j] = sc.nextInt();

        H = sc.nextInt();
        W = sc.nextInt();
        sy = sc.nextInt() - 1;
        sx = sc.nextInt() - 1;
        fy = sc.nextInt() - 1;
        fx = sc.nextInt() - 1;

        bfs();
        System.out.println(dist[fy][fx] - 1);
    }

    static boolean check(int y, int x) {
        for(int i = y; i < y + H; i++) {
            if(i < 0 || i >= N || map[i][x] == 1) return false;
            if(x + W - 1 >= M || map[i][x + W - 1] == 1) return false;
        }

        for(int i = x; i < x + W; i++) {
            if(i < 0 || i >= M || map[y][i] == 1) return false;
            if(y + H - 1 >= N || map[y + H - 1][i] == 1) return false;
        }

        return true;
    }

    static void bfs() {
        Queue<Point> q = new LinkedList<>();
        q.add(new Point(sy, sx));
        dist[sy][sx] = 1;
        while(!q.isEmpty()) {
            Point now = q.poll();
            if(now.y == fy && now.x == fx) return;
            for(int d = 0; d < 4; d++) {
                int ny = now.y + dy[d];
                int nx = now.x + dx[d];
                if(ny < 0 || nx < 0 || ny >= N || nx >= M || map[ny][nx] == 1 || dist[ny][nx] != 0) continue;
                if(!check(ny, nx)) continue;
                dist[ny][nx] = dist[now.y][now.x] + 1;
                q.add(new Point(ny, nx));
            }
        }
    }

    static class Point {
        int y, x;
        Point(int y, int x) {
            this.y = y;
            this.x = x;
        }
    }
}

 

---

⏱️ 결과

 

 

 

Uploaded by Notion2Tistory v1.1.0