<Algorithm> 23. 1085번 직사각형에서 탈출하기

1. 1085번 직사각형에서 탈출하기

• 상하좌우 경계선이 4개이므로 4개를 모두 구해서 최소값을 판별하는 것도 가능

• BFS를 이용하여 풀이, 주의할점은 꼭지점으로 주어지는 경우 배열로 할경우 +1에 값이 차이날 수 있음

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75

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 Main {       public static void main(String[] args) throws IOException {         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));         StringTokenizer st = new StringTokenizer(br.readLine());                  int x = Integer.parseInt(st.nextToken());         int y = Integer.parseInt(st.nextToken());         int w = Integer.parseInt(st.nextToken());         int h = Integer.parseInt(st.nextToken());                  int[][] dist = new int[w+1][h+1];         // 배열을 좌표평면으로 생각했을 경우 +1을 해주어야 한다                  for(int i = 0; i < w+1; i++) {             for(int j = 0; j < h+1; j++) {                 dist[i][j] = -1;             }         }                  int[] dx = {0, 0, 1,-1};         int[] dy = {1,-1, 0, 0};                  dist[x][y] = 0;         Queue<Location> queue = new LinkedList<>();          queue.add(new Location(x, y));                  int min = Integer.MAX_VALUE;                  while(!queue.isEmpty()) {             Location location = queue.remove();             x = location.x;             y = location.y;                          for(int i = 0; i < 4; i++) {                 int nx = x + dx[i];                 int ny = y + dy[i];                                  if(nx < w+1 && ny < h+1 && nx >=0 && ny >=0) {                     if(dist[nx][ny] == -1) {                         if(nx == w || nx == 0 || ny == h || ny == 0) {                             dist[nx][ny] = dist[x][y] + 1;                             if(dist[nx][ny] < min) min = dist[nx][ny];                             // 4개중 최소값                                                      } else {                             dist[nx][ny] = dist[x][y] + 1;                             queue.add(new Location(nx, ny));                         }                     }                 }                              }         }                  System.out.println(min);              }      }   class Location{     int x,y;     public Location(int x, int y) {         this.x = x;         this.y = y;     } } Colored by Color Scripter

cs