1. 문제
https://www.acmicpc.net/problem/5427
2. 풀이 과정
상근이가 이미 지나간 곳은 불이 번져도 상근이를 따라 잡을 수 없기 때문에, 불이 번지는 건 빈칸만 고려해주었다. 빈칸을 누가 먼저 가냐만 보면 된다.
상근이가 현재 갈 수 있는 위치와 불이 방금 번진 위치를 모두 queue에 넣고, 4방향 탐색으로 갈 수 있는 곳에 표시를 해준다. 이때, 상근이는 불이 다 번지고 난 후에 움직이기 때문에 처음 상근이의 위치는 queue의 마지막에 넣어주도록 해서 구현한다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
static int w, h, result;
static int[] dx = {1, 0, -1, 0};
static int[] dy = {0, -1, 0, 1};
static char[][] arr;
static Queue<int[]> q;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
StringBuilder sb = new StringBuilder();
int T = Integer.parseInt(br.readLine());
for(int test_case = 1; test_case <= T; test_case++) {
st = new StringTokenizer(br.readLine());
w = Integer.parseInt(st.nextToken());
h = Integer.parseInt(st.nextToken());
arr = new char[h][w];
q = new LinkedList<>();
result = 0;
int x = 0, y = 0;
for(int i = 0; i < h; i++) {
String str = br.readLine();
for(int j = 0; j < w; j++) {
arr[i][j] = str.charAt(j);
if(arr[i][j] == '*'){
q.add(new int[]{i, j});
}
else if(arr[i][j] == '@'){
x = i;
y = j;
}
}
}
q.add(new int[]{x, y});
sb.append(simulation() ? result : "IMPOSSIBLE").append("\n");
}
System.out.println(sb);
br.close();
}
public static boolean simulation() {
while(!q.isEmpty()){
result++;
for(int i=0, size = q.size(); i<size; i++){
int[] now = q.poll();
for(int j=0; j<4; j++){
int nx = now[0] + dx[j];
int ny = now[1] + dy[j];
if(nx < 0 || nx >= h || ny < 0 || ny >= w){
if(arr[now[0]][now[1]] == '@'){
return true;
}
continue;
}
if(arr[nx][ny] != '.'){continue;}
arr[nx][ny] = arr[now[0]][now[1]];
q.add(new int[]{nx, ny});
}
}
}
return false;
}
}
결과
'코딩문제풀이 > Baekjoon' 카테고리의 다른 글
[Java] 백준 1890번 : 점프 (0) | 2023.01.13 |
---|---|
[Java] 백준 21610번 : 마법사 상어와 비바라기 (0) | 2023.01.10 |
[Java] 백준 16987번 : 계란으로 계란치기 (0) | 2023.01.08 |
[Java] 백준 1926번 : 그림 (0) | 2023.01.06 |
[Java] 백준 19583번 : 싸이버개강총회 (0) | 2023.01.05 |