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

문제설명

www.acmicpc.net/problem/16973

16973번: 직사각형 탈출

 

기본아이디어

N x M 크기의 격자판에서 H x M 크기의 직사각형이 원하는 위치까지 도달하는데 걸리는 최소값을 구하는 문제입니다.일단 BFS탐색을 한다고 생각을 하고 이동할 때 어떻게 검사할지 생각했습니다. 

 

그림을 그려보면서 생각한 것은 가려는 방향의 끝 한줄을 빼면 모든 좌표는 이미 직사각형 내부에 있는 점으로 이동을 한다는 것이었습니다. 즉 가려는 방향의 한줄만 검사를 하면 ( N x M 안에 있는지, 갈수없는 좌표인지 ) 이동을 할 수 있다는 것입니다. 이 아이디어를 그대로 구현했습니다.

구현코드

public static void main(String[] args) throws IOException {
        StringTokenizer st = new StringTokenizer(input.readLine());
 
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
 
        map = new int[N][];
        for(int i = 0; i < N; i++){
            st = new StringTokenizer(input.readLine());
            int[] temp = new int[M];
            for(int j = 0; j < M; j++)
                temp[j] = Integer.parseInt(st.nextToken());
            map[i] = temp;
        }
        st = new StringTokenizer(input.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;
 
        System.out.println(bfs());
 
    }
    static int N, M, H, W;
    static int[][] map;
    static int sr, sc, fr, fc;
    static int[] dr = {-1, 1, 0, 0};    // 상하좌우
    static int[] dc = {0, 0, -1, 1};    // 상하좌우
    static int bfs(){
        int result = 0;
        Queue<int[]> queue = new LinkedList<>();
        boolean[][] visited = new boolean[N][M];
        queue.add(new int[]{sr,sc});
        visited[sr][sc] = true;
        while (!queue.isEmpty()){
            result++;
            int size = queue.size();
            for(int i = 0; i < size; i++){
                int[] loc = queue.poll();
                for(int d = 0; d < 4; d++){
                    int nr = loc[0] + dr[d];
                    int nc = loc[1] + dc[d];
                    if(isIn(nr,nc) && !visited[nr][nc] && isOk(nr, nc, d)){
                        if(nr == fr && nc == fc)
                            return result;
                        visited[nr][nc] = true;
                        queue.add(new int[]{nr,nc});
                    }
                }
            }
        }
        return -1;
    }
    static boolean isOk(int r, int c, int dir){
        // dir = 0, 1, 2, 3 -> 상하좌우
        int start_row = r;
        int end_row = r + H - 1;
        int start_col = c;
        int end_col = c + W - 1;
 
        switch (dir){
            case 0:
                end_row = start_row;
                break;
            case 1:
                start_row = end_row;
                break;
            case 2:
                end_col = start_col;
                break;
            case 3:
                start_col = end_col;
                break;
        }
        for(int i = start_row; i <= end_row; i++){
            for(int j = start_col; j <= end_col; j++){
                if(!isIn(i, j)) {
                    return false;
                }
                if(map[i][j] == 1) {
                    return false;
                }
            }
        }
        return true;
    }
 
    static boolean isIn(int r, int c){
        return r >= 0 && r < N && c >= 0 && c < M;
    }
 
 
 
 
 

 

정리, 기억할 내용

1. 주어지는 좌표가 (0,0) ~ (N-1, M-1) 까지인지, (1,1) ~ (N,M) 까지인지 확인하자.

2. 그림을 그려보자.