반응형
11-23 02:05
Today
Total
«   2024/11   »
1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
관리 메뉴

개발하는 고라니

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

Programming/백준

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

조용한고라니 2021. 4. 15. 13:11
반응형
 

16973번: 직사각형 탈출

크기가 N×M인 격자판에 크기가 H×W인 직사각형이 놓여 있다. 격자판은 크기가 1×1인 칸으로 나누어져 있다. 격자판의 가장 왼쪽 위 칸은 (1, 1), 가장 오른쪽 아래 칸은 (N, M)이다. 직사각형의 가장

www.acmicpc.net


[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));
    }
}
반응형

'Programming > 백준' 카테고리의 다른 글

[백준] 11021번 : A + B - 7  (0) 2021.04.28
[백준] 16932번 : 모양 만들기  (0) 2021.04.15
[백준] 14923번 : 미로 탈출  (0) 2021.04.15
[백준] 18119번 : 단어 암기  (0) 2021.04.09
[백준] 16947번 : 서울 지하철 2호선  (0) 2021.04.08
Comments