[Baekjoon] 18405_경쟁적 전염

Gold V

문제(출처: https://www.acmicpc.net/problem/18405)

---

<경쟁적 전염>

 

문제 풀이

 

번호가 낮은 종류의 바이러스부터 증식시키기 위해서 우선순위 큐를 사용하여 해결하였다.

 

 - my solution (Java)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class _18405_ { // 경쟁적 전염
	static int[] dx= {-1,1,0,0}; // 상하좌우
	static int[] dy= {0,0,-1,1};
	static PriorityQueue<int[]>queue;
	static int n, map[][];

	public static void main(String[] args) throws IOException {
		BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=new StringTokenizer(bf.readLine());
		
		n=Integer.parseInt(st.nextToken());
		int k=Integer.parseInt(st.nextToken());
		
		queue=new PriorityQueue<>(new Comparator<int[]>() {
			@Override
			public int compare(int[] o1, int[] o2) {
				return o1[0]-o2[0];
			}
		});
		
		map=new int[n][n];
		boolean[][]depth=new boolean[n][n];
		for(int i=0; i<n; i++) {
			st=new StringTokenizer(bf.readLine());
			for(int j=0; j<n; j++) {
				map[i][j]=Integer.parseInt(st.nextToken());
				if(map[i][j]!=0) { // 바이러스 번호와 위치 저장
					queue.add(new int[] {map[i][j],i,j});
					depth[i][j]=true;
				}
			}
		}
		
		st=new StringTokenizer(bf.readLine());
		int s=Integer.parseInt(st.nextToken()); // 초
		int x=Integer.parseInt(st.nextToken());
		int y=Integer.parseInt(st.nextToken());
		
		if(s!=0) {
			search(); 
			for(int i=0; i<s-1; i++) {
				for(int j=0; j<n; j++) {
					for(int l=0; l<n; l++) {
						if(depth[j][l]==false && map[j][l]>0) { // 아직 증식하지 않은 바이러스
							depth[j][l]=true;
							queue.add(new int[] {map[j][l], j, l});
						}
					}
				}
				search(); 
				if(map[x-1][y-1]>0) break;
			}
		}
		System.out.println(map[x-1][y-1]);
	}

	private static void search() {
		while(!queue.isEmpty()) {
			int[] temp=queue.poll();
			for(int i=0; i<4; i++) {
				int a=temp[1]+dx[i];
				int b=temp[2]+dy[i];
				if(a>=0 && a<n && b>=0 && b<n && map[a][b]==0) {
					map[a][b]=temp[0];
				}
			}
		}
	}
}

 

•  Main
  • n, k입력
  • map : 시험관의 정보
  • depth : 매 초마다 방문 여부 확인하기 위해 표시
  • map을 입력받을 때 바이러스가 존재하면 우선순위 큐에 [바이러스 번호, x좌표,  y좌표]로 넣기
  • 0초인 경우에는 바로 answer 출력!
  • 0초가 아닌 경우 search() 호출 + s-1초만큼 아직 증식하지 않은 바이러스 찾아서 반복! 이미 (x-1, y-1) 자리에 바이러스가 존재한다면 중간에 break! (=이미 바이러스가 존재하면 다른 바이러스가 들어갈 수 없기 때문)
• search ( )
  • queue가 빌 때까지 반복 
    -> queue에서 poll 한 값 위치에서 상하좌우를 판별하여 아직 바이러스가 없는 곳이라면 map에 바이러스 증식 표시

---

생각🤔

 

분명 답이 맞는데 왜 틀렸을까... 한참 봐도 찾을 수 없었다.

아무리 봐도 찾을 수 없었다..!!

 

반례 질문을 찾아본 결과 S가 0초일 때를 고려하지 못한 것이었다.

S!=0 조건을 하나 추가하고 나서야 바로 해결 ~_~

 

---