-
문제
지훈이는 미로에서 일을 한다. 지훈이를 미로에서 탈출하도록 도와주자!
미로에서의 지훈이의 위치와 불이 붙은 위치를 감안해서 지훈이가 불에 타기전에 탈출할 수 있는지의 여부, 그리고 얼마나 빨리 탈출할 수 있는지를 결정해야한다.
지훈이와 불은 매 분마다 한칸씩 수평또는 수직으로(비스듬하게 이동하지 않는다) 이동한다.
불은 각 지점에서 네 방향으로 확산된다.
지훈이는 미로의 가장자리에 접한 공간에서 탈출할 수 있다.
지훈이와 불은 벽이 있는 공간은 통과하지 못한다.
입력
입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다.다음 입력으로 R줄동안 각각의 미로 행이 주어진다.
각각의 문자들은 다음을 뜻한다.
* #: 벽
* .: 지나갈 수 있는 공간
* J: 지훈이의 미로에서의 초기위치 (지나갈 수 있는 공간)
* F: 불이 난 공간
* J는 입력에서 하나만 주어진다.풀이
탐색을 동시에 진행해야 하는 문제이다.
주의할 점은 불이 번진 후에 지훈이가 움직일 수 있다.
또한 탈출 조건은 가장자리에 도달할 때의 경우이다.
따라서 x와 y좌표가 각각 R과 C에 위치한다면 탈출하는 것이다(물론 인덱스값의 보정이 필요).초기의 불의 위치는 여러개가 나올 수 있다.
불의 위치를 Queue에 넣어준 후 bfs를 진행한다.지훈이와 불 동시에 bfs를 진행해야 한다.
FireQueue의 크기만큼 visited 여부에 따라 동서남북 이동을 체크해준다.
이후 queue에 넣어 탐색을 진행한다.주의할점은 FireQueue의 size를 미리 구한 후에 반복을 돌려야 한다.
반복중에 FireQueue의 size를 그대로 사용하면 queue에 추가하게되어 크기가 늘어나 불에 대한 bfs()만을 진행하게 되기 때문이다.
이렇게 같은 절차로 지훈의 이동을 수행해준다.class Main { static String[][] map; static int R; static int C; static int[] x_loc = {0, 0, 1, -1}; static int[] y_loc = {1, -1, 0, 0}; static Queue<Loc> fireQueue = new LinkedList<>(); public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String[] str = br.readLine().split(" "); R = Integer.parseInt(str[0]); C = Integer.parseInt(str[1]); map = new String[R][C]; boolean[][] visited = new boolean[R][C]; int startX = 0; int startY = 0; for(int i = 0; i < R; i++) { str = br.readLine().split(""); for(int j = 0; j < C; j++) { map[i][j] = str[j]; if (map[i][j].equals("J")) { startX = i; startY = j; } if (map[i][j].equals("F")) { fireQueue.add(new Loc(i, j)); visited[i][j] = true; } } } int count = bfs(startX, startY, visited); if (count != 0) { System.out.println(count); } else { System.out.println("IMPOSSIBLE"); } } static int bfs(int startX, int startY, boolean[][] visited) { Queue<Loc> queue = new LinkedList<>(); int count = 0; visited[startX][startY] = true; map[startX][startY] = "."; queue.add(new Loc(startX, startY)); while(!queue.isEmpty()) { int fireQueueSize = fireQueue.size(); int queueSize = queue.size(); // 불 번짐 for(int idx = 0; idx < fireQueueSize; idx++) { Loc fireLoc = fireQueue.poll(); for(int i = 0; i < 4; i++) { int fireLocX = fireLoc.x + x_loc[i]; int fireLocY = fireLoc.y + y_loc[i]; if (check(fireLocX, fireLocY, visited) && map[fireLocX][fireLocY].equals(".")) { visited[fireLocX][fireLocY] = true; map[fireLocX][fireLocY] = "F"; fireQueue.add(new Loc(fireLocX, fireLocY)); } } } // 사람 이동 for(int idx = 0; idx < queueSize; idx++) { Loc queueLoc = queue.poll(); if (isEscape(queueLoc.x, queueLoc.y)) { count++; return count; } for(int i = 0; i < 4; i++) { int locX = queueLoc.x + x_loc[i]; int locY = queueLoc.y + y_loc[i]; if (check(locX, locY, visited) && map[locX][locY].equals(".")) { visited[locX][locY] = true; queue.add(new Loc(locX, locY)); } } } count++; } return 0; } static boolean check(int x, int y, boolean[][] visited) { return (x >= 0 && x < R) && (y >= 0 && y < C) && !visited[x][y]; } static boolean isEscape(int x, int y) { return (x == 0 || x == R - 1) || (y == 0 || y == C - 1); } static class Loc { int x; int y; public Loc(int x, int y) { this.x = x; this.y = y; } } }
728x90'알고리즘' 카테고리의 다른 글
[BOJ] 연산자끼워넣기 (0) 2023.12.20 [BOJ] 빗물 (1) 2023.12.19 [BOJ] 상범빌딩 (0) 2023.11.29 [BOJ] 음식물 피하기 (1) 2023.11.27 [BOJ] 숫자 고르기 (1) 2023.11.25