[백준 24513] 좀비 바이러스 (Java)

문제 링크: https://www.acmicpc.net/problem/24513

24513번: 좀비 바이러스

1. 주의할 점

- BFS 종료시점을 잘 정하여 TLE가 나지 않도록 한다

- 동시에 도달할 경우, 어떻게 처리할 것인가

 

2. 구현

- Y, X, 바이러스 번호, 해당 칸에 도달하기까지 걸린 시간의 형태를 저장하는 Info를 이용하여 BFS를 수행한다

- Check[y][x][flag] 배열을 통해 flag 바이러스가 [y][x]에 도달하기까지 걸린 시간을 저장한다

- Arr[][] 배열에 마을에 대한 정보를 담고, 바이러스가 존재한다면 Queue에 추가하고 Check[][][] 값을 0으로 초기화한다

- BFS() 함수를 통해 Queue에 원소가 남아있다면 Arr[][] 값을 변경하고 바이러스의 수를 담은 Cnt[] 배열도 수정한다.

- 전파를 시도할 때, 동일 바이러스와 다른 바이러스의 전파 여부를 파악하여 전파 여부를 결정한다

- 동일 바이러스라면 cv+1과 비교를 하고 다른 바이러스라면 cv와 비교한다(동시에 퍼졌을 경우를 고려하기 위해) 

 

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

public class Main {
	static class Info{
		int y,x,flag,val;
		public Info(int y, int x, int flag, int val) {
			this.y=y;
			this.x=x;
			this.flag=flag;
			this.val=val;
		}
	};
	
	static int row,col;
	static int arr[][];
	static int check[][][];
	static int cnt[];		//치료제 보유 마을,1,2,3번 바이러스 감염마을 수
	final static int dx[] = {0,1,0,-1};
	final static int dy[] = {-1,0,1,0};
	final static int MAXI = 987654321;
	static Queue<Info> q;
	
	static void bfs() {
		
		while(!q.isEmpty()) {
		    Info ii = q.poll();
		    int cx = ii.x;
		    int cy = ii.y;
		    int cf = ii.flag;
		    int cv = ii.val;
		    int v1 = check[cy][cx][1]==MAXI ? 0 : 1;
		    int v2 = check[cy][cx][2]==MAXI ? 0 : 2;
		    arr[cy][cx]=v1+v2;
		    cnt[v1+v2]++;
		    if(v1+v2==3) continue;
		    for(int i=0;i<4;i++){
		        int nx = cx+dx[i];
		        int ny = cy+dy[i];
		        if(nx>=0 && ny>=0 && nx<col && ny<row && arr[ny][nx]==0 && check[ny][nx][cf]>cv+1 && check[ny][nx][3-cf]>cv){
		            check[ny][nx][cf]=cv+1;
		            if(check[ny][nx][3-cf]==MAXI) q.offer(new Info(ny,nx,cf,cv+1));
		        }
		    }
		}
	}
	
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String str = br.readLine();
		StringTokenizer st = new StringTokenizer(str);
		row = Integer.parseInt(st.nextToken());
		col = Integer.parseInt(st.nextToken());
		
		//초기화
		arr = new int[row][col];
		q = new LinkedList<>();
		cnt = new int[4];
		check = new int[row][col][3];
		for(int i=0;i<row;i++)
		    for(int j=0;j<col;j++)
		        for(int k=0;k<3;k++)
		            check[i][j][k]=MAXI;

		for(int i=0;i<row;i++) {
			str = br.readLine();
			st = new StringTokenizer(str);
			for(int j=0;j<col;j++) {
				int val = Integer.parseInt(st.nextToken());
				arr[i][j] = val;
				if(0<val && val<3){
				    q.offer(new Info(i,j,val,0));
				    check[i][j][val]=0;
				}
			}
		}
		bfs();
		System.out.println(cnt[1]+" "+cnt[2]+" "+cnt[3]);
	}
}