문제
시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율
| 1 초 | 256 MB | 37117 | 9871 | 6578 | 24.587% |
문제
상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다.
매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에는 불이 붙지 않는다. 상근이는 동서남북 인접한 칸으로 이동할 수 있으며, 1초가 걸린다. 상근이는 벽을 통과할 수 없고, 불이 옮겨진 칸 또는 이제 불이 붙으려는 칸으로 이동할 수 없다. 상근이가 있는 칸에 불이 옮겨옴과 동시에 다른 칸으로 이동할 수 있다.
빌딩의 지도가 주어졌을 때, 얼마나 빨리 빌딩을 탈출할 수 있는지 구하는 프로그램을 작성하시오.
입력
첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스는 최대 100개이다.
각 테스트 케이스의 첫째 줄에는 빌딩 지도의 너비와 높이 w와 h가 주어진다. (1 ≤ w,h ≤ 1000)
다음 h개 줄에는 w개의 문자, 빌딩의 지도가 주어진다.
- '.': 빈 공간
- '#': 벽
- '@': 상근이의 시작 위치
- '*': 불
각 지도에 @의 개수는 하나이다.
출력
각 테스트 케이스마다 빌딩을 탈출하는데 가장 빠른 시간을 출력한다. 빌딩을 탈출할 수 없는 경우에는 "IMPOSSIBLE"을 출력한다.
풀이
BFS로 풀 수 있는 문제였다.
- 배열을 벽, 불, 상근이, 빈 공간 으로 나눠서 값을 업데이트 해준다.
- 움직일 수 있는 사람이 있는지 확인
- 현재 시점에 불들을 4 방향으로 불을 퍼뜨린다 (시간이 없을 경우 한번에 불 다붙이고 끝나버림)
- 현재 시점에 사람을 4 방향으로 이동시킨다.
- 만약 사람이 배열의 끝 부분에 도착했다면 가장 빨리 도착한 경우 업데이트 해준다.
푸는데 중요했던 부분은 두가지가 있었다.
불이 2개가 붙어있다면, 주기마다 2개의 불을 다 이동시켜야 하는 것
빌딩을 탈출하는데에 가장 빠른 시간을 출력하는 것
package com.company.baekjoon;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
public class B5427 {
static final int WALL = -2;
static final int FIRE = -1;
static final int EMPTY_SPACE = 0;
static final int PERSON = 1;
static int[] dx = new int[] {-1,1,0,0};
static int[] dy = new int[] {0,0,-1,1};
static int[][] graph;
static Queue<int[]> fires = new LinkedList<>();
static Queue<int[]> person = new LinkedList<>();
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int T = Integer.parseInt(br.readLine());
for (int i = 0; i < T; i++) {
String[] size = br.readLine().split(" ");
int w = Integer.parseInt(size[0]);
int h = Integer.parseInt(size[1]);
graph = new int[h][w];
fires.clear();
person.clear();
int answer = Integer.MAX_VALUE;
int time = 0;
for (int j = 0; j < h; j++) {
char[] s = br.readLine().toCharArray();
for (int k = 0; k < s.length; k++) {
if (s[k] == '#') {
graph[j][k] = WALL;
} else if (s[k] == '.') {
graph[j][k] = EMPTY_SPACE;
} else if (s[k] == '*') {
graph[j][k] = FIRE;
fires.add(new int[] {j,k,0});
} else {
graph[j][k] = PERSON;
person.add(new int[]{j,k,0});
}
}
}
// 불 먼저 움직이고 사람 움직이기
while (!person.isEmpty()) {
while (fires.peek() != null && fires.peek()[2] == time ) {
int[] fire = fires.poll();
for (int j = 0; j < dx.length; j++) {
int cy = fire[0] + dy[j];
int cx = fire[1] + dx[j];
if (cx < 0 || cy < 0 || cx >= w || cy >= h) continue;
if (graph[cy][cx] == FIRE) continue;
if (graph[cy][cx] != WALL) {
graph[cy][cx] = FIRE;
fires.add(new int[]{cy, cx, fire[2] + 1});
}
}
}
while (person.peek() != null && person.peek()[2] == time) {
int[] p = person.poll();
for (int j = 0; j < dx.length; j++) {
int cy = p[0] + dy[j];
int cx = p[1] + dx[j];
if (cx < 0 || cy < 0 || cx >= w || cy >= h) {
answer = Math.min(answer,p[2]);
break;
}
if (graph[cy][cx] == EMPTY_SPACE) {
graph[cy][cx] = PERSON;
person.add(new int[]{cy, cx, p[2] + 1});
}
}
}
time++;
}
if (answer == Integer.MAX_VALUE)
sb.append("IMPOSSIBLE").append("\n");
else
sb.append(answer+1).append("\n");
}
System.out.println(sb);
}
}'알고리즘' 카테고리의 다른 글
| [SWEA] 5658. [모의 SW 역량테스트] 보물상자 비밀번호 자바 풀이 (2) | 2023.10.14 |
|---|---|
| [백준] 14502번 연구소 자바 풀이 (1) | 2023.10.08 |
| [백준] 21609 상어 중학교 자바 풀이 (1) | 2023.10.05 |
| [백준] 1283번 단축키 지정 풀이 (0) | 2023.09.19 |
| [백준] 20055번 컨베이어 벨트 위의 로봇 자바 풀이 (0) | 2023.09.14 |
