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

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

16973번: 직사각형 탈출

문제풀이

이번 문제는 BFS문제에 범위를 추가하여 진행하는 문제였습니다.

주어지는 직사각형의 가로길이와 세로길이를 받아서 해당 범위내에 벽이 있는지 체크하면서 진행합니다.

이 문제같은경우 유의해야할 사항은,
직사각형을 돌면서 벽이 있는지 체크하면 모든 BFS 경우마다 NXM 만늠 연산을 수행하므로 시간초과가 날 수 있습니다.
해결방법은, 벽의 위치를 list에 넣어서, 벽의 위치가  x ~ x + H, y ~ y + W 에 있다면 직사각형 안에 벽이 있는것이므로 실패처리합니다.

위의 방식으로 진행하면 해결할 수 있습니다.

 

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
	
	public static int N,M;
	public static int[][] map;
	public static boolean[][] visited;
	public static int H,W,sr,sc,fr,fc;
	public static int result = 0;
	public static ArrayList<Integer[]> arr = new ArrayList<>();
    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());
    	
    	map = new int[N+1][M+1];
    	visited = new boolean[N+1][M+1];
    	for(int i=1;i<=N;i++) {
    		st = new StringTokenizer(br.readLine());
    		for(int j=1;j<=M;j++) {
    			map[i][j] = Integer.parseInt(st.nextToken());
    			if(map[i][j] == 1) {
    				arr.add(new Integer[] {i,j});
    			}
    		}
    	}
    	
    	st = new StringTokenizer(br.readLine());
    	H = Integer.parseInt(st.nextToken());
    	W = Integer.parseInt(st.nextToken());
    	sr = Integer.parseInt(st.nextToken());
    	sc = Integer.parseInt(st.nextToken());
    	fr = Integer.parseInt(st.nextToken());
    	fc = Integer.parseInt(st.nextToken());
    	
    	bfs();
    	
    	if(result!= 0) {
    		System.out.println(result);
    	}else {
    		System.out.println("-1");
    	}
    	
    }
    
    public static void bfs() {
    	int[] dx = {-1,1,0,0};
    	int[] dy = {0,0,-1,1};
    	Queue<Node> q = new LinkedList<>();
    	q.offer(new Node(sr, sc, 0));
    	visited[sr][sc] = true;
    	
    	while(!q.isEmpty()) {
    		Node temp = q.poll();
    		int x = temp.x;
    		int y = temp.y;
    		int cnt = temp.cnt;
    		
    		if(x == fr && y == fc) {
    			result = cnt;
    			return;
    		}
    		
    		for(int dir=0;dir<4;dir++) {
    			int nx = x + dx[dir];
    			int ny = y + dy[dir];
    			
    			if( nx < 1 || nx + H - 1> N || ny < 1 || ny + W - 1 > M) continue;
    			if(Check(nx, ny) == false) continue;
    			if(visited[nx][ny] == true) continue;
    			if( map[nx][ny] == 1 )continue;
    			q.offer(new Node(nx, ny, cnt + 1));
    			visited[nx][ny] = true;
    		}
    	}
    }
    
    public static boolean Check(int x, int y) {
    	for(int i=0;i<arr.size();i++) {
    		int wallx = arr.get(i)[0];
    		int wally = arr.get(i)[1];
    		
    		if( x <= wallx && wallx <= x + H - 1 && y <= wally && wally <= y + W - 1) {
    			return false;
    		}
    	}
    	return true;
    }
   
}

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