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

[문제링크]

16973번: 직사각형 탈출

 

0. 최단 거리 탐색 문제, BFS

 

1. 큰 덩어리가 움직이므로, 4방향 각각 이동 가능한지 판단하는 함수 chk를 만든다

 

2. 맵 크기가 1000*1000이므로 초기값은 1000000보다 큰 임의의 수를 선택

 

3. 시작지점부터 BFS로 탐색 진행

 

4. 최종 지점의 값이 초기값이라면 도달 불가하므로 -1을 출력, 값이 변했다면 해당 값을 출력한다

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main{
	static int[][] map;
	static int[][] answer;
	static int H,W,Sx,Sy,Ex,Ey;
	static int ans;
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int n = pint(st.nextToken());
		int m = pint(st.nextToken());
		map = new int[n][m];
		answer = new int[n][m];
		
		for (int i = 0; i < n; i++) {
			Arrays.fill(answer[i], 1000001);
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < m; j++) {
				map[i][j] = pint(st.nextToken());
			}
		}
		st = new StringTokenizer(br.readLine());
		H = pint(st.nextToken()); W = pint(st.nextToken());
		Sx = pint(st.nextToken())-1; Sy = pint(st.nextToken())-1;
		Ex = pint(st.nextToken())-1; Ey = pint(st.nextToken())-1;
		
		Queue<int[]> qu = new LinkedList<int[]>();
		qu.offer(new int[] {Sx,Sy,0});
		answer[Sx][Sy]=0;
		//bfs
		while(!qu.isEmpty()) {
			int[] cur = qu.poll();
			if(cur[0]+H < n && answer[cur[0]+1][cur[1]]>cur[2]+1 && chk(cur[0], cur[1], 0) ) {
				answer[cur[0]+1][cur[1]]=cur[2]+1;
				qu.offer(new int[] {cur[0]+1, cur[1], cur[2]+1});
			}
			if(cur[0]-1 >=0 && answer[cur[0]-1][cur[1]]>cur[2]+1 && chk(cur[0], cur[1], 1) ) {
				answer[cur[0]-1][cur[1]]=cur[2]+1;
				qu.offer(new int[] {cur[0]-1, cur[1], cur[2]+1});
			}
			if(cur[1]-1 >=0 && answer[cur[0]][cur[1]-1]>cur[2]+1 && chk(cur[0], cur[1], 2) ) {
				answer[cur[0]][cur[1]-1]=cur[2]+1;
				qu.offer(new int[] {cur[0], cur[1]-1, cur[2]+1});
			}
			if(cur[1]+W < m && answer[cur[0]][cur[1]+1]>cur[2]+1 && chk(cur[0], cur[1], 3) ) {
				answer[cur[0]][cur[1]+1]=cur[2]+1;
				qu.offer(new int[] {cur[0], cur[1]+1, cur[2]+1});
			}
		}
		System.out.println(answer[Ex][Ey]>1000000 ? -1 : answer[Ex][Ey]);
	}

	static boolean chk(int x, int y, int type) {
		boolean returnV = true;
		if(type==0) {
			//chk down
			for (int i = y; i < y+W; i++) {
				if(map[x+H][i]==1)returnV=false;
			}
		}
		else if(type==1){
			//chk up
			for (int i = y; i < y+W; i++) {
				if(map[x-1][i]==1)returnV=false;
			}
		}
		else if(type==2){
			//chk left
			for (int i = x; i < x+H; i++) {
				if(map[i][y-1]==1)returnV=false;
			}
		}
		else if(type==3){
			//chk right
			for (int i = x; i < x+H; i++) {
				if(map[i][y+W]==1)returnV=false;
			}
		}return returnV;
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

결과 화면