[BOJ] 18405번 경쟁적 전염 (Java/BFS)

문제

백준 18405번 경쟁적 전염

---

풀이

1. 바이러스의 위치와 번호를 저장하기 위한 Virus 클래스를 정의합니다.
   • 이때 바이러스 번호를 오름차순으로 정렬하기 위해 Comparable 인터페이스를 사용합니다.
2. 주어진 시험관의 정보를 입력받습니다.
   • 바이러스가 있을 경우 해당 바이러스의 번호와 좌표를 virus 리스트에 추가합니다.
3. 바이러스는 작은 번호부터 순서대로 증식하므로 virus 배열을 바이러스 번호 기준으로 정렬해줍니다.
4. 정렬된 바이러스 리스트를 queue에 삽입합니다.
5. BFS를 통해 S초 동안 바이러스를 증식시키고, (X, Y) 좌표의 바이러스 번호를 출력합니다.

소스 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

	static class Virus implements Comparable<Virus> {
		int num, x, y;

		public Virus(int num, int x, int y) {
			super();
			this.num = num;
			this.x = x;
			this.y = y;
		}

		@Override
		public int compareTo(Virus o) {
			return this.num - o.num;
		}

	}

	static List<Virus> virus;
	static Queue<Virus> queue;

	static int[] dx = { -1, 1, 0, 0 };
	static int[] dy = { 0, 0, -1, 1 };

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		int N = Integer.parseInt(st.nextToken()); // 시험관 크기
		int K = Integer.parseInt(st.nextToken()); // K 종류의 바이러스
		int arr[][] = new int[N][N];
		virus = new ArrayList<Virus>();
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());

				if (arr[i][j] != 0) {
					virus.add(new Virus(arr[i][j], i, j));
				}
			}
		}

		st = new StringTokenizer(br.readLine());
		int S = Integer.parseInt(st.nextToken());
		int X = Integer.parseInt(st.nextToken()) - 1;
		int Y = Integer.parseInt(st.nextToken()) - 1;
		// input end

		Collections.sort(virus);
		queue = new LinkedList<Virus>();
		for (int i = 0; i < virus.size(); i++) {
			queue.offer(virus.get(i));
		}

		// BFS
		for (int s = 0; s < S; s++) {
			if (queue.isEmpty())
				break;
			int size = queue.size();
			for (int c = 0; c < size; c++) {
				Virus cur = queue.poll();

				for (int d = 0; d < 4; d++) {
					int nx = cur.x + dx[d];
					int ny = cur.y + dy[d];

					if (nx < 0 || nx >= N || ny < 0 || ny >= N)
						continue;

					if (arr[nx][ny] == 0) { // 조건 없어서 메모리초과 발생
						arr[nx][ny] = cur.num;
						queue.offer(new Virus(cur.num, nx, ny));
					}
				}
			}
		}

		System.out.println(arr[X][Y]);

	}

}

오류 기록

BFS 진행 시 시험관 칸에 바이러스가 존재하지 않을 경우에만 새로운 바이러스를 증식시킬 수 있다는 조건을 추가하지 않아 메모리초과 오류가 발생했습니다.