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

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

 

생각보다 어렵게 풀린 문제 ㅜ_ㅜ

이 문제의 핵심 포인트는 다음과 같다

1. 직사각형 중 첫번째 좌표의 범위를 잘 잡기

(1~N-H+1,1~M-W+1)

2. 사각형의 범위 안에 1이 있으면 안되는데 이를 판별할때

이중 for문으로 만들어진 사각형마다 확인하면 시간초과가 발생한다

따라서 먼저 1(벽)을 ArrayList에 추가한 후에 벽의 좌표를 꺼내서

사각형의 범위 안에 있는지 역으로 확인해야 함!!

=> walls에 벽의 x좌표, y좌표를 추가함

 

 

1번 조건을 고려하지 않았을 때 반럐

5 5

0 0 0 0 0

0 0 0 0 0

0 0 1 0 0

0 0 0 0 0

0 0 0 0 0

2 2 1 1 5 4

정답: -1

 

내 답안

import java.io.*;
import java.util.*;

public class Main {
    static int N,M,h,w;
    static int[][] graph;
    static boolean[][] visited;
    static ArrayList<int[]> walls;
    static int[] dx = {0,0,1,-1};
    static int[] dy = {1,-1,0,0};
    static boolean check(int x, int y){
        for(int i=0;i<walls.size();i++){
            int wallX = walls.get(i)[0];
            int wallY = walls.get(i)[1];
            if(wallX>=x&&wallX<x+h && wallY>=y&&wallY<y+w)
                return false;
        }
        return true;
    }

    static int bfs(int startX, int startY, int Fx, int Fy){
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{startX, startY, 0});
        visited[startX][startY] = true;

        while(!q.isEmpty()){
            int[] now = q.poll();
            int nowX = now[0];
            int nowY = now[1];
            int nowCnt = now[2];

            if(nowX==Fx && nowY==Fy){
                return nowCnt;
            }

            for(int i=0;i<4;i++){
                int nextX = nowX+dx[i];
                int nextY = nowY+dy[i];

                if(nextX>=1&&nextX<=N-h+1 && nextY>=1&&nextY<=M-w+1){
                    if(!visited[nextX][nextY]) {
                        if(check(nextX,nextY)){
                            visited[nextX][nextY] = true;
                            q.add(new int[]{nextX, nextY, nowCnt + 1});
                        }
                    }
                }
            }

        }
        return -1;
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        graph = new int[N+1][M+1];
        visited = new boolean[N+1][M+1];
        walls = new ArrayList<>();

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

        st = new StringTokenizer(br.readLine());
        h = Integer.parseInt(st.nextToken());
        w = Integer.parseInt(st.nextToken());
        int Sx = Integer.parseInt(st.nextToken());
        int Sy = Integer.parseInt(st.nextToken());
        int Fx = Integer.parseInt(st.nextToken());
        int Fy = Integer.parseInt(st.nextToken());


        System.out.println(bfs(Sx, Sy, Fx, Fy));

    }

}