[백준] 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 qu = new LinkedList(); 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); } }

결과 화면

from http://nato-blog.tistory.com/147 by ccl(S) rewrite - 2021-11-05 08:27:54