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

문제

16973번: 직사각형 탈출 (acmicpc.net)

풀이

• BFS를 이용해 Sr, Sc에서 시작해서 상하좌우로 한 칸씩 이동 가능한지 확인하며 모든 좌표를 탐색한다.
  • 작은 직사각형 범위 안에 벽(1)이 있거나 직사각형이 격자의 범위를 벗어나면 해당 경우는 이동할 수 없음
  • 이미 방문한 좌표이면 이동할 수 없음
• 시작 좌표가 Fr, Fc에 도달하면 지금까지 움직인 거리를 출력한다.

 

직사각형 범위 안에 벽이 있는지 확인할 때, 직사각형의 모든 좌표를 탐색하면 시간초과가 발생한다. 

//시간초과
import java.awt.*;
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 boj_16973 {
    static int N, M, H, W, Sr, Sc, Fr, Fc, ans=Integer.MAX_VALUE;
    static int[][] board;
    static int[] dx, dy;
    static boolean[][] visited;
    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());

        board = new int[N][M];
        for(int i=0; i<N; i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<M; j++){
                board[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;

        dx = new int[H]; //행
        dy = new int[W]; //열

        for(int i=0; i<H; i++)
            dx[i] = i;
        for(int i=0; i<W; i++)
            dy[i] = i;

        visited = new boolean[N][M];

        bfs(Sr, Sc, 0);
        if(ans == Integer.MAX_VALUE){
            System.out.println(-1);
        }else System.out.println(ans);


    }
    static void bfs(int x, int y, int cnt){
        Queue<Point> q = new LinkedList<>();
        q.add(new Point(x, y, cnt));
        visited[x][y] = true;

        while(!q.isEmpty()){
            Point now = q.poll();

            if(now.x==Fr && now.y==Fc){
                if(ans>now.cnt) ans=now.cnt;
                return;
            }

            boolean isValid = true;

            for(int i=0; i<H; i++){
                for(int j=0; j<W; j++){

                    int nx = now.x + dx[i];
                    int ny = now.y + dy[j];

                    if(nx<0 || nx>=N || ny<0 || ny>=M || board[nx][ny]==1){
                        //범위를 벗어나거나 벽을 만남
                        isValid = false;
                        break;
                    }
                }
                if(!isValid) break;
            }

            if(isValid){ 
                //직사각형 범위 모두 만족하면 한 칸 이동
                int[] dx = {0, 0, 1, -1};
                int[] dy = {1, -1, 0, 0};

                for(int i=0; i<4; i++){
                    int nx = now.x + dx[i];
                    int ny = now.y + dy[i];

                    if(nx<0 || nx>=N || ny<0 || ny>=M
                            || board[nx][ny]==1 || visited[nx][ny])
                        continue;

                    q.add(new Point(nx, ny, now.cnt+1));
                    visited[nx][ny] = true;

                }
            }
        }

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

 

따라서 벽의 좌표를 리스트에 저장해두고 벽이 직사각형 안에 포함되는지 확인해야 한다.

코드

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

public class boj_16973 {
    static int N, M, H, W, Sr, Sc, Fr, Fc, ans=Integer.MAX_VALUE;
    static int[][] board;
    static boolean[][] visited;
    static ArrayList<Point> walls;
    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());

        walls = new ArrayList<>();
        board = new int[N][M];

        for(int i=0; i<N; i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<M; j++){
                board[i][j] = Integer.parseInt(st.nextToken());
                if(board[i][j]==1)
                    walls.add(new Point(i, j));
            }
        }

        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;

        visited = new boolean[N][M];

        bfs(Sr, Sc, 0);
        if(ans == Integer.MAX_VALUE){
            System.out.println(-1);
        }else System.out.println(ans);


    }
    static void bfs(int x, int y, int cnt){
        Queue<Point> q = new LinkedList<>();
        q.add(new Point(x, y, cnt));
        visited[x][y] = true;

        while(!q.isEmpty()){
            Point now = q.poll();

            if(now.x==Fr && now.y==Fc){
                if(ans>now.cnt) ans=now.cnt;
                return;
            }

            //이동 가능한 경우, 한 칸 이동
            for(int i=0; i<4; i++){
                int[] dx = {0, 0, 1, -1};
                int[] dy = {1, -1, 0, 0};

                int nx = now.x + dx[i];
                int ny = now.y + dy[i];

                //좌표가 격자에서 벗어남
                if(nx<0 || nx>=N || ny<0 || ny>=M || visited[nx][ny])
                    continue;

                boolean isValid = true;

                //직사각형 크기가 격자에서 벗어남
                if(nx+H>N || ny+W>M)
                    continue;

                //직사각형 내부에 벽이 있음
                for(int j=0; j<walls.size(); j++){
                    int wallX = walls.get(j).x;
                    int wallY = walls.get(j).y;

                    if(wallX<nx+H && wallY<ny+W && wallX>=nx && wallY>=ny){
                        isValid = false;
                        break;
                    }
                }
                if(!isValid) continue;

                q.add(new Point(nx, ny, now.cnt+1));
                visited[nx][ny] = true;
            }

        }

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