Q.16973 자바 : 직사각형 탈출(G4)

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

크기가 N×M인 격자판에 크기가 H×W인 직사각형이 놓여 있다.

격자판은 크기가 1×1인 칸으로 나누어져 있다.

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

직사각형의 가장 왼쪽 위칸은 (Sr, Sc)에 있을 때,

이 직사각형의 가장 왼쪽 위칸을 (Fr, Fc)로 이동시키기 위한 최소 이동 횟수를 구해보자.

 

격자판의 각 칸에는 빈 칸 또는 벽이 있다.

직사각형은 벽이 있는 칸에 있을 수 없다. 또한, 직사각형은 격자판을 벗어날 수 없다.

직사각형은 한 번에 왼쪽, 오른쪽, 위, 아래 중 한 방향으로 한 칸 이동시킬 수 있다.

직사각형의 크기와 좌표를 주고, 장애물을 피해 원하는 좌표로 이동하면 되는 문제이다.

일하면서 틈틈히 남는 시간에 풀어서 거의 이틀에 걸쳐서 풀었다.

처음에는 재귀를 통해서 풀어보려고 했지만, 계속 실패해서 접근방법을 바꿔야겠다는 생각이 들었고

결국에는 큐를 이용한 BFS를 이용해 풀었다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

class Main {
    static BufferedReader br;
    static StringBuffer sb;
    static int[][] Plane;
    static boolean[][] Visited;
    static int result = -1;
    static int H, W, Fr, Fc, N, M, Sr, Sc;

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        sb = new StringBuffer();
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        Plane = new int[N][M];
        Visited = new boolean[N][M];

        for (int i=0; i<N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j=0; j<M; j++) {
                Plane[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        st = new StringTokenizer(br.readLine());
        H = Integer.parseInt(st.nextToken());
        W = Integer.parseInt(st.nextToken());
        Sr = Integer.parseInt(st.nextToken())-1;
        Sc = Integer.parseInt(st.nextToken())-1;
        Fr = Integer.parseInt(st.nextToken())-1;
        Fc = Integer.parseInt(st.nextToken())-1;

        BFS();
        System.out.println(result);
    }

    static int[] dr = {0, 1, 0, -1};
    static int[] dc = {1, 0, -1, 0};
    public static void BFS() {

        Visited[Sr][Sc] = true;
        Queue<Point> queue = new LinkedList<>();

        queue.add(new Point(Sr, Sc, 0));
        while (!queue.isEmpty()) {

            Point point = queue.poll();
            for (int i=0; i<4; i++) {
                int prevR = point.r + dr[i];
                int prevC = point.c + dc[i];

                if (prevR == Fr && prevC == Fc) {
                    result = point.move + 1;
                    return;
                }
                if (prevR < 0 || prevC < 0 || (prevR + H) > N || (prevC + W) > M || Visited[prevR][prevC]) {
                    continue;
                }
                if (Plane[prevR][prevC] == 0) {
                    if (check(prevR, prevC)) {
                        queue.add(new Point(prevR, prevC, point.move+1));
                        Visited[prevR][prevC] = true;
                    }
                }

            }
        }
    }

    public static boolean check(int r, int c) {

        for (int i=0; i<H; i++) {
            for (int j=0; j<W; j++) {
                if (Plane[r + i][c + j] == 1) {
                    return false;
                }
            }
        }
        return true;
    }

    public static class Point {
        int r;
        int c;
        int move;
        Point(int r, int c, int move) {
            this.r = r;
            this.c = c;
            this.move = move;
        }
    }
}

1. 입력 좌표들을 어떻게 받아야 되는지(문제는 1.1부터 시작하지만, 실제 배열은 0.0부터이므로),

2. 직사각형이 움직였을 때 벽 존재 여부를 어떻게 검사해야 하는지,

3. 그리고 확인한 곳을 재방문하지 않으려면 어떻게 해야하는지

세 가지가 구현을 할 때 신경써야 할 점 이라고 생각했다.

 

1번 내용은 처음에 햇갈려서 고생을 좀 많이 했다. 처음에는 배열 선언할 때 1씩 크게 잡은 뒤

실제 구현을 문제에서 제시한 좌표와 동일하게 구현했는데, 이러다 보니 더 햇갈려져서

그냥 문제에서 제시한 좌표 - 1을 하는 방식으로 구현했다.

 

2번 내용은 y축으로 1 이동할 경우 이동한 만큼만 검사하는 방식으로 구현하려 했지만

코드가 더 복잡해지는 것 같아 그냥 이동할 때 마다 직사각형에 포함되는 모든 좌표에

벽이 존재하는지 여부를 검사했다.

 

3번 내용은 처음에는 Plane[][] 이차원 배열에 방문한 곳은 '2'라고 표시하는 방식을 사용했다가

그냥 boolean[][] 배열을 만들어 검사하는게 좀 더 나아보여 그냥 따로 배열을 선언했다.

---

사실 내가 적은 위의 내용들은 재귀함수를 이용해 구현하면서 좀 더 삽질을 오래 했는데,

혹시 조건이 문제인가 해서 queue를 이용해 구현한 위 코드를 이용해 먼저 정답 처리가 된 뒤

다시 재귀함수로 구현해 봤지만, 제공한 테스트 케이스에서는 원하는 답이 나오지만

실제로 제출을 하면 내가 뭔가를 놓치고 있는지 계속 실패해 포기했다.

개인적으로 이럴 때 백준에서 실패한 테스트 케이스를 알려주지 않는게 아쉽다.

하지만 테스트 케이스를 알려주면 정답이 아니지만 그 케이스만 맞춰서 하게 되므로

제공하지 않는 것도 이해가 가긴 한다.