[백준] 16973번 : 직사각형 탈출

16973번: 직사각형 탈출

---

[BFS]

나는 입력으로 주어지는 지도를 저장할 때, int[ ][ ]가 아닌 boolean[ ][ ]에 저장했다. 이유는 추후 연산이 오래 걸릴 것을 감안해서이다. 아무래도 숫자 비교 연산보다 boolean 연산이 훨씬 빠르다고 생각했다.

 

어쨋든 N x M 직사각형 안에 H x W 크기의 직사각형이 하나 더 들어있는데, 벽을 피해서 가장 왼쪽 위의 꼭지점을 목적지로 이동하는 문제라고 파악했다. 매번 직사각형을 옮기며 모든 꼭지점에 벽이 있는지를 보는 것 보다, 직사각형의 테두리만 검사하면 된다.

 

0	0	0	0	0	0
0	0	0	0	0	0
0	0	0	0	1	0
0	0	0	0	0	0
1	0	0	0	0	0
0	0	0	0	0	0

색이 칠해진 곳을 직사각형의 테두리라고 보면, 내부는 신경쓸 필요 없다. 오직 테두리가 다음 상하좌우로 이동할 때 그 곳에 벽이 있는지, 범위가 벗어나진 않는지만 체크해서 BFS를 수행하면 된다.

# Code </>

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

    static class Point{
        int y, x, move;

        public Point(int yy, int xx, int move){
            y=yy;
            x=xx;
            this.move=move;
        }
    }
    static int n, m, h, w;
    static int[] Y = {-1,1,0,0}, X = {0,0,-1,1};
    static boolean[][] map = new boolean[1001][1001];
    static boolean[][] visit = new boolean[1001][1001];

    static boolean isAnyWall(int upY, int upX, int downY, int downX){

        for(int i=upX; i<=downX; i++)
            if(!map[upY][i] || !map[downY][i]) return false;

        for(int i=upY; i<=downY; i++)
            if(!map[i][upX] || !map[i][downX]) return false;

        return true;
    }

    static int BFS(int startY, int startX, int endY, int endX){
        Queue<Point> Q = new LinkedList<>();

        visit[startY][startX] = true;
        Q.add(new Point(startY, startX, 0));

        while(!Q.isEmpty()){
            Point p = Q.poll();
            //가장 왼쪽 위에 꼭지점 좌표
            int y = p.y;
            int x = p.x;

            if(y == endY && x == endX)
                return p.move;

            //가장 오른쪽 아래 꼭지점 좌표
            int by = y + h - 1;
            int bx = x + w - 1;

            for(int a=0; a<4; a++){
                int ny = y+Y[a];
                int nx = x+X[a];

                int nBy = by+Y[a];
                int nBx = bx+X[a];

                //범위를 벗어나는지 check
                if(ny < 1 || nx < 1 || ny > n || nx > m || visit[ny][nx]) continue;
                if(nBy > n || nBx > m) continue;
                //다음 이동할 곳에 벽이 있는지 check
                if(!isAnyWall(ny, nx, nBy, nBx)) continue;

                visit[ny][nx] = true;
                Q.add(new Point(ny, nx, p.move + 1));
            }
        }

        return -1;
    }

    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());

        for(int i=1; i<=n; i++){
            st = new StringTokenizer(br.readLine());

            for(int j=1; j<=m; j++){
                if(Integer.parseInt(st.nextToken()) == 0)
                    map[i][j] = true;
            }
        }

        st = new StringTokenizer(br.readLine());

        h = Integer.parseInt(st.nextToken());
        w = Integer.parseInt(st.nextToken());

        int y = Integer.parseInt(st.nextToken());
        int x = Integer.parseInt(st.nextToken());

        int endY = Integer.parseInt(st.nextToken());
        int endX = Integer.parseInt(st.nextToken());

        System.out.println(BFS(y, x, endY, endX));
    }
}

위 코드는 이동하는 방향이 어디든 위 아래 양옆 테두리를 모두 벽이 있는지 검사한 것이고, 

아래 코드는 이동하는 방향에 대한 테두리만 벽이 있는지 검사한 코드인데,

 

결과를 보았을 때 시간과 메모리의 차이가 크게 나지 않았다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

    static class Point{
        int y, x, move;

        public Point(int yy, int xx, int move){
            y=yy;
            x=xx;
            this.move=move;
        }
    }
    static int n, m, h, w;
    static int[] Y = {-1,1,0,0}, X = {0,0,-1,1};
    static boolean[][] map = new boolean[1001][1001];
    static boolean[][] visit = new boolean[1001][1001];

    static boolean isAnyWall(int upY, int upX, int downY, int downX, int a){

/*        for(int i=upX; i<=downX; i++)
            if(!map[upY][i] || !map[downY][i]) return false;

        for(int i=upY; i<=downY; i++)
            if(!map[i][upX] || !map[i][downX]) return false;*/

        if(a == 0){
            for(int i=upX; i<=downX; i++)
                if(!map[upY][i]) return false;
        }
        else if(a == 1){
            for(int i=upX; i<=downX; i++)
                if(!map[downY][i]) return false;
        }
        else if(a == 2){
            for(int i=upY; i<=downY; i++)
                if(!map[i][upX]) return false;
        }
        else{
            for(int i=upY; i<=downY; i++)
                if(!map[i][downX]) return false;
        }

        return true;
    }

    static int BFS(int startY, int startX, int endY, int endX){
        Queue<Point> Q = new LinkedList<>();

        visit[startY][startX] = true;
        Q.add(new Point(startY, startX, 0));

        while(!Q.isEmpty()){
            Point p = Q.poll();
            int y = p.y;
            int x = p.x;

            if(y == endY && x == endX)
                return p.move;

            int by = y + h - 1;
            int bx = x + w - 1;

            for(int a=0; a<4; a++){
                int ny = y+Y[a];
                int nx = x+X[a];

                int nBy = by+Y[a];
                int nBx = bx+X[a];

                if(ny < 1 || nx < 1 || ny > n || nx > m || visit[ny][nx]) continue;
                if(nBy > n || nBx > m) continue;

                if(!isAnyWall(ny, nx, nBy, nBx)) continue;

                visit[ny][nx] = true;
                Q.add(new Point(ny, nx, p.move + 1));
            }
        }

        return -1;
    }

    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());

        for(int i=1; i<=n; i++){
            st = new StringTokenizer(br.readLine());

            for(int j=1; j<=m; j++){
                if(Integer.parseInt(st.nextToken()) == 0)
                    map[i][j] = true;
            }
        }

        st = new StringTokenizer(br.readLine());

        h = Integer.parseInt(st.nextToken());
        w = Integer.parseInt(st.nextToken());

        int y = Integer.parseInt(st.nextToken());
        int x = Integer.parseInt(st.nextToken());

        int endY = Integer.parseInt(st.nextToken());
        int endX = Integer.parseInt(st.nextToken());

        System.out.println(BFS(y, x, endY, endX));
    }
}