[BOJ] 24513 좀비 바이러스

24513 좀비 바이러스

난이도 : 골드 4
유형 : BFS

https://www.acmicpc.net/problem/24513

문제

여기 $N$ x $M$ 격자 모양의 마을이 있다. 어느 날 세상에 좀비 바이러스가 창궐하여 바이러스가 빠르게 퍼져나가버린다. 바이러스에 대해 조사한 결과 세 종류의 바이러스가 존재했으며 각각 $1$번, $2$번, $3$번으로 번호를 매겼다.

바이러스의 특징은 다음과 같다.

 $1$번과 $2$번 바이러스는 치사율은 낮지만 전염성이 강해 상하좌우에 인접해 있는 마을로 동시에 퍼져나가며 한 마을을 완전히 감염시키는 데 1시간 걸린다.

• 마을이 완전히 감염되어야 다른 마을로 퍼져나갈 수 있으며 다른 바이러스가 완전히 감염시킨 마을은 침범하지 않는다.
• 마을이 한 바이러스에 완전히 감염되기 전에 다른 종류의 바이러스가 마을에 도착하면 $3$번 바이러스가 만들어진다.
•  $3$번 바이러스는 치사율이 높은 만큼 전염성이 약해 감염된 마을에서 더 이상 퍼지지 않는다.
• 치료제를 갖고 있는 마을은 감염시킬 수 없다.
  
  
  

입력

첫째 줄에 $N$($2≤N≤1\,000$)과 $M$($2≤M≤1\,000$)이 주어진다.

둘째 줄부터 $N$개의 줄에 걸쳐 마을의 상태가 $M$개 주어진다. 마을의 상태는 다음과 같이 이루어져 있다.

-$1$: 치료제를 가진 마을

•  $0$: 아직 감염되지 않은 마을
•  $1$: $1$번 바이러스에 감염된 마을
•  $2$: $2$번 바이러스에 감염된 마을

 $1$번 바이러스와 $2$번 바이러스에 감염된 마을은 각각 하나씩만 주어진다.

출력

 $1$번, $2$번, $3$번 바이러스에 감염된 마을의 수를 공백으로 구분하여 한 줄에 출력한다.

풀이

전형적인 BFS 문제인데 완전히 감염시키는 데 1시간 걸린다는 조건과 완전히 감염되기 전에 다른 종류의 바이러스가 도착하면 3번 바이러스가 만들어지는 조건을 잘 따져봐야 한다.

처음 map 배열에 주어진 입력값과 함께 시간도 같이 넣어주고, 바이러스를 입력 받았을 때 큐에 넣어줬다.
입력을 다 받아 준 다음 bfs를 돌면서 바이러스를 퍼트릴 때 큐에 담겼던 현재 시간에서 +1해서 시간을 넣어주었다.
따라서 감염이 이미 되었는데 완전히 감염되었는지 여부를 시간의 차이로 판별할 수 있고, 바이러스 변이를 시킬 수 있게 되는 것이다.

코드

package DFS와BFS;

import java.io.*;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

/**
 * BOJ_24513_G4_좀비 바이러스
 * @author mingggkeee
 * BFS
 */

public class BOJ_24513 {
	
	static class Virus{
		int virus;
		int time;
		int r;
		int c;
		
		public Virus(int virus, int time) {
			this.virus = virus;
			this.time = time;
		}
		
		public Virus(int r, int c, int virus, int time) {
			super();
			this.r= r;
			this.c= c;
			this.virus = virus;
			this.time = time;
		}
	}
	
	static int R, C;
	static Virus[][] map;
	static int[][] dir = {{0,1},{0,-1},{1,0},{-1,0}};
	static Queue<Virus> queue = new LinkedList<>();
	static boolean[][] isVisited;
	
	public static void main(String[] args) throws IOException{
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		R = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());
		
		map = new Virus[R][C];
		isVisited = new boolean[R][C];
		
		for(int r=0; r<R; r++) {
			st = new StringTokenizer(br.readLine());
			for(int c=0; c<C; c++) {
				map[r][c] = new Virus(Integer.parseInt(st.nextToken()), 0);
				if(map[r][c].virus == 1 || map[r][c].virus==2) {
					queue.offer(new Virus(r,c,map[r][c].virus, 0));
				}
			}
		}
		
		bfs();
		
		int count1 = 0;
		int count2 = 0;
		int count3 = 0;
		
		for(int r=0; r<R; r++) {
			for(int c=0; c<C; c++) {
				if(map[r][c].virus == 1) {
					count1++;
				}
				else if(map[r][c].virus == 2) {
					count2++;
				}
				else if(map[r][c].virus == 3) {
					count3++;
				}
			}
		}
		
		System.out.println(count1+" "+count2+" "+count3);
	}
	
	static void bfs() {
		
		while(!queue.isEmpty()) {
			
			Virus now = queue.poll();
			int time = now.time;
			isVisited[now.r][now.c] = true;
			// 3번바이러스는 퍼지지 않는다.
			if(map[now.r][now.c].virus == 3)
				continue;
			
			for(int i=0; i<4; i++) {
				int nr = now.r + dir[i][0];
				int nc = now.c + dir[i][1];
				int virus = now.virus;
				
				if(nr<0 || nc<0 || nr>=R || nc>=C || isVisited[nr][nc] || map[nr][nc].virus == -1)
					continue;
				
				// 아직 감염되지 않았을 경우
				if(map[nr][nc].virus == 0) {
					map[nr][nc].virus = virus;
					map[nr][nc].time = now.time+1;
					queue.offer(new Virus(nr, nc, map[nr][nc].virus, map[nr][nc].time));
				} 
				// 감염이 되어있는데 완전히 감염되었는지 여부를 확인
				else if(map[nr][nc].virus != virus && map[nr][nc].virus != 3) {
					// 완전히 감염되지 않았을 경우 3번 바이러스로 변이(시간의 차이가 1밖에안난다면 아직 완전히 감염되지 않은 것이다.)
					if(map[nr][nc].time > time && map[nr][nc].time - time == 1) {
						map[nr][nc].virus = 3;
					}
					
				}
				
				
			}
			
			
		}
		
		
	}
	
	

}