처음에 구현했을 때 테케는 다 맞는데 계속 메모리 초과가 됐다..
무슨 조건을 못잡아서 그런가 싶었는데 방문이 중복되는 문제가 있었다.
box[curr.x][curr.y] = -1로 방문 여부를 체크했지만,
BFS가 진행되면서 이미 방문한 노드를 큐에 다시 추가하는 경우가 발생했다.
따라서, 큐에 불필요하게 많은 노드가 추가되면서 메모리 사용량이 급격히 증가했다.
▼ 기존 코드
더보기
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
class Pair1 {
int x, y;
public Pair1(int x, int y) {
this.x = x;
this.y = y;
}
}
public class BOJ7576 {
int[][] box;
int[][] dist;
int minDay = 0;
// 상 우 하 좌
int[] dx = {0, 1, 0, -1};
int[] dy = {-1, 0 , 1, 0};
public void solution() throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
int M = Integer.parseInt(st.nextToken());
int N = Integer.parseInt(st.nextToken());
Queue<Pair1> q = new LinkedList<>();
box = new int[N][M];
dist = new int[N][M];
for (int i = 0; i < N; i++) {
StringTokenizer st2 = new StringTokenizer(br.readLine(), " ");
for (int j = 0; j < M; j++) {
box[i][j] = Integer.parseInt(st2.nextToken());
// 익은 토마토인 경우
if (box[i][j] == 1) {
q.add(new Pair1(i, j));
}
}
}
// BFS
while (!q.isEmpty()) {
Pair1 curr = q.remove();
box[curr.x][curr.y] = -1; // 방문 체크
for (int k = 0; k < 4; k++) {
int nextX = curr.x + dx[k];
int nextY = curr.y + dy[k];
// 범위를 벗어나는 경우
if (nextX < 0 || nextX >= N || nextY < 0 || nextY >= M) {
continue;
}
// -1을 마주친 경우
if (box[nextX][nextY] == -1) {
continue;
}
// 로직
q.add(new Pair1(nextX, nextY));
dist[nextX][nextY] = dist[curr.x][curr.y] + 1;
}
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (box[i][j] == 0) {
System.out.println(-1);
return;
}
minDay = Math.max(minDay, dist[i][j]);
}
}
System.out.println(minDay);
}
public static void main(String[] args) throws Exception {
new BOJ7576().solution();
}
}
아래가 정답 코드인데 중요한 부분을 다시 보겠다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
class Pair1 {
int x, y;
public Pair1(int x, int y) {
this.x = x;
this.y = y;
}
}
public class BOJ7576 {
int[][] box;
int[][] dist;
int minDay = 0;
// 상 우 하 좌
int[] dx = {0, 1, 0, -1};
int[] dy = {-1, 0 , 1, 0};
public void solution() throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
int M = Integer.parseInt(st.nextToken());
int N = Integer.parseInt(st.nextToken());
Queue<Pair1> q = new LinkedList<>();
box = new int[N][M];
dist = new int[N][M];
for (int i = 0; i < N; i++) {
StringTokenizer st2 = new StringTokenizer(br.readLine(), " ");
for (int j = 0; j < M; j++) {
box[i][j] = Integer.parseInt(st2.nextToken());
// 익은 토마토인 경우
if (box[i][j] == 1) {
q.add(new Pair1(i, j));
}
if (box[i][j] == 0) {
dist[i][j] = -1; // 익지 않은 토마토
}
}
}
// BFS
while (!q.isEmpty()) {
Pair1 curr = q.remove();
box[curr.x][curr.y] = -1; // 방문 체크
for (int k = 0; k < 4; k++) {
int nextX = curr.x + dx[k];
int nextY = curr.y + dy[k];
// 범위를 벗어나는 경우
if (nextX < 0 || nextX >= N || nextY < 0 || nextY >= M) {
continue;
}
// 이미 방문했거나 빈 칸인 경우
if (dist[nextX][nextY] != -1) {
continue;
}
// 로직
q.add(new Pair1(nextX, nextY));
dist[nextX][nextY] = dist[curr.x][curr.y] + 1;
}
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (box[i][j] == 0 && dist[i][j] == -1) {
System.out.println(-1);
return;
}
minDay = Math.max(minDay, dist[i][j]);
}
}
System.out.println(minDay);
}
public static void main(String[] args) throws Exception {
new BOJ7576().solution();
}
}
1. 익지 않은 토마토인 경우
우선, dist[i][j] 배열에 모두 -1로 초기화 해준다.
for (int i = 0; i < N; i++) {
StringTokenizer st2 = new StringTokenizer(br.readLine(), " ");
for (int j = 0; j < M; j++) {
box[i][j] = Integer.parseInt(st2.nextToken());
// 익은 토마토인 경우
if (box[i][j] == 1) {
q.add(new Pair1(i, j));
}
// 익지 않은 토마토인 경우
if (box[i][j] == 0) {
dist[i][j] = -1;
}
}
}
2. 이미 방문했거나 빈 칸인 경우
만약 방문한 경우 dist[nextX][nextY]가 -1이 아닌 거리일테니 그런 경우 continue로 넘겨준다.
dist[nextX][nextY]가 0이라는 의미는 위 for문에서 익은 토마토도, 익지 않은 토마토도 아닌, 아예 존재하지 않음(-1) 이므로continue 하게 된다.
for (int k = 0; k < 4; k++) {
int nextX = curr.x + dx[k];
int nextY = curr.y + dy[k];
// 범위를 벗어나는 경우
if (nextX < 0 || nextX >= N || nextY < 0 || nextY >= M) {
continue;
}
// 이미 방문했거나 빈 칸인 경우
if (dist[nextX][nextY] != -1) {
continue;
}
// 로직
q.add(new Pair1(nextX, nextY));
dist[nextX][nextY] = dist[curr.x][curr.y] + 1;
}
}