[JAVA] 백준 24513 좀비 바이러스

24513번: 좀비 바이러스

풀이 방법

bfs가 한턴씩 지날 때마다 몇번째 방문인지 저장하기 위해 copy 배열을 만들었다. 

처음은 첫번째 방문으로 가정해 1을 넣어주었다.

 

처음

왼쪽은 첫번째 턴, 오른쪽은 두번째 턴을 돌았을 때의 결과

이렇게 턴을 돌 때마다 copy에 현재 몇번째 턴인지 저장해두었다.

만약 map[nx][ny]를 방문했을 때 copy[nx][ny]에 저장된 값과 현재 턴수가 같고,

map[nx][ny]와 map[x][y]이 다르면 침범이 일어났다는 뜻이므로 map[nx][ny] 값을 3으로 바꿔주었다.

 

자바 코드

import java.io.*;
import java.util.*;

public class Main {
	static class Pos {
		int x;
		int y;
		int c;

		public Pos(int x, int y, int c) {
			this.x = x;
			this.y = y;
			this.c = c;
		}
	}

	static StringTokenizer st;
	static int N, M;
	static int[][] map, copy;
	static Queue<Pos> q;
	static int[][] dir = { { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } };

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		map = new int[N][M];
		copy = new int[N][M];
		q = new LinkedList<>();
		for (int n = 0; n < N; n++) {
			st = new StringTokenizer(br.readLine());
			for (int m = 0; m < M; m++) {
				map[n][m] = Integer.parseInt(st.nextToken());
				if (map[n][m] == 1 || map[n][m] == 2) {
					q.add(new Pos(n, m, 1));
				}
			}
		} // 입력 완료
		virus();
		int result[] = new int[4];
		for (int n = 0; n < N; n++) {
			for (int m = 0; m < M; m++) {
				if (map[n][m] == 1)
					result[1] += 1;
				else if (map[n][m] == 2)
					result[2] += 1;
				else if (map[n][m] == 3)
					result[3] += 1;
			}
		}
		System.out.print(result[1] + " " + result[2] + " " + result[3]);
	}

	private static void virus() {
		while (!q.isEmpty()) {
			Pos cur = q.poll();
			int x = cur.x;
			int y = cur.y;
			int c = cur.c;
			if (map[x][y] == 1 || map[x][y] == 2) {
				for (int i = 0; i < dir.length; i++) {
					int nx = x + dir[i][0];
					int ny = y + dir[i][1];
					if (nx >= 0 && ny >= 0 && nx < N && ny < M && map[nx][ny] != -1 && map[nx][ny] != 3) {
						if (map[nx][ny] == 0) {
							map[nx][ny] = map[x][y];
							copy[nx][ny]=c;
							q.add(new Pos(nx, ny, c + 1));
						} else if (copy[nx][ny]==c && map[nx][ny] != map[x][y]) {
							map[nx][ny] = 3;
						}
					}
				}
			}
		}
	}
}