백준 5427번
https://www.acmicpc.net/problem/5427
BFS 문제이다.
메모리가 자꾸 부족하다고 나와서 고생했다.
que
가 너무 커지지 않도록 하는게 관건인 것 같다
isVisited
를 사용해서 중복 방문피하기
불은 fires
배열을 통해서 관리하고 que
에서는 하나만 들어가도록 하기
que
에 들어가는 객체에 너무 많은 데이터를 넣으면 안되는것 같다.
import java.io.*;
import java.util.LinkedList;
import java.util.StringTokenizer;
public class Main {
// input
private static BufferedReader br;
// variables
private static int N, M;
private static char[][] map = new char[1001][1001];
private static final int[] dirX = {0, 1, 0, -1}; // 우 하 좌 상
private static final int[] dirY = {1, 0, -1, 0}; // 우 하 좌 상
private static Coordinate start;
private static LinkedList<Coordinate> fires;
private static class Coordinate {
int x;
int y;
int time;
private Coordinate(int x, int y) {
this.x = x;
this.y = y;
}
public Coordinate(int x, int y, int time) {
this.x = x;
this.y = y;
this.time = time;
}
} // End of Coordinate
public static void main(String[] args) throws IOException {
br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int t = Integer.parseInt(br.readLine());
while (t-- > 0) {
input();
bw.write(solve());
}
bw.close();
} // End of main()
private static String solve() {
StringBuilder sb = new StringBuilder();
int ret = BFS();
if (ret == -1) {
sb.append("IMPOSSIBLE");
} else {
sb.append(ret);
}
sb.append('\n');
return sb.toString();
} // End of solve()
private static int BFS() {
LinkedList<Coordinate> que = new LinkedList<>();
boolean[][] isVisited = new boolean[N][M];
que.offer(new Coordinate(-1, -1));
que.offer(new Coordinate(start.x, start.y));
isVisited[start.x][start.y] = true;
while (!que.isEmpty()) {
Coordinate current = que.poll();
if (current.x == -1) {
burn();
if (!que.isEmpty()) {
que.offer(current);
}
continue;
}
for (int i = 0; i < 4; i++) {
int nextX = dirX[i] + current.x;
int nextY = dirY[i] + current.y;
if (nextX < 0 || nextX >= N || nextY < 0 || nextY >= M) {
// 탈출
return current.time + 1;
}
if (isVisited[nextX][nextY] || map[nextX][nextY] != '.') continue;
isVisited[nextX][nextY] = true;
que.offer(new Coordinate(nextX, nextY, current.time + 1));
}
}
return -1;
} // End of BFS()
private static void burn() {
int size = fires.size();
for (int i = 0; i < size; i++) {
Coordinate current = fires.poll();
for (int j = 0; j < 4; j++) {
int nextX = dirX[j] + current.x;
int nextY = dirY[j] + current.y;
if (nextX >= 0 && nextX < N && nextY >= 0 && nextY < M && map[nextX][nextY] == '.') {
fires.offer(new Coordinate(nextX, nextY));
map[nextX][nextY] = '*';
}
}
}
} // End of burn()
private static void input() throws IOException {
StringTokenizer st = new StringTokenizer(br.readLine());
M = Integer.parseInt(st.nextToken());
N = Integer.parseInt(st.nextToken());
fires = new LinkedList<>();
for (int i = 0; i < N; i++) {
String temp = br.readLine();
for (int j = 0; j < M; j++) {
map[i][j] = temp.charAt(j);
if (map[i][j] == '@') {
map[i][j] = '.';
start = new Coordinate(i, j);
} else if (map[i][j] == '*') {
fires.offer(new Coordinate(i, j));
}
}
}
} // End of input()
} // End of Main class