[BaekJoon] 18405 경쟁적 전염 (Java)

1.  문제 링크

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

2.  문제

요약

• NxN 크기의 시험관에서 특정한 위치에는 바이러스가 존재할 수 있고, 모든 바이러스는 1번부터 K번까지의 바이러스 종류 중 하나에 속합니다.
• 시험관에 존재하는 모든 바이러스는 1초마다 상,하,좌,우의 방향으로 증식해 나가고, 매 초마다 번호가 낮은 종류의 바이러스부터 먼저 증식합니다.
• 증식 과정에서 이미 특정한 칸에 어떠한 바이러스가 존재한다면, 그 곳에는 다른 바이러스가 들어갈 수 없습니다.
• 시험관의 크기와 바이러스의 위치 정보가 주어졌을 때, S초가 지난 후에 (X, Y)에 존재하는 바이러스의 종류를 구하는 문제입니다.
• 입력
  • 첫 번째 줄에 1보다 크거나 같고 200보다 작거나 같은 N과 1보다 크거나 같고 1,000보다 작거나 같은 K가 주어집니다.
  • 두 번째 줄부터 N개의 줄에는 시험관의 정보가 주어집니다.
    • 각 행은 N개의 원소로 구성되고, 각 위치에 존재하는 바이러스의 번호가 주어집니다.
  • N + 2번째 줄에는 0보다 크거나 같고 10,000보다 작거나 같은 S, 1보다 크거나 같고 N보다 작거나 같은 X, Y가 주어집니다.
• 출력: 첫 번째 줄에 S초 뒤에 (X, Y)에 존재하는 바이러스의 종류를 출력합니다. 만약 해당 위치에 바이러스가 존재하지 않는다면 0을 출력합니다.

3.  소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
	static int[][] map;
	static boolean[][] visited;
	static int second;
	static ArrayList<Point>[] virus_points;
	
	public void findVirusType() {
		int[] dx = {-1, 0, 1, 0};
		int[] dy = {0, -1, 0, 1};
		Queue<Point> queue = new LinkedList<Point>();
		for(int i = 1; i < virus_points.length; i++) {
			for(int j = 0; j < virus_points[i].size(); j++) {
				queue.add(virus_points[i].get(j));
			}
		}
		int len = queue.size();
		for(int i = 0; i < second; i++) {
			for(int j = 0; j < len; j++) {
				Point cur_point = queue.poll();
				for(int l = 0; l < 4; l++) {
					int cx = cur_point.x + dx[l];
					int cy = cur_point.y + dy[l];
					if(cx >= 0 && cx < map.length && cy >= 0 && cy < map.length) {
						if(!visited[cx][cy] && map[cx][cy] == 0) {
							map[cx][cy] = map[cur_point.x][cur_point.y];
							visited[cx][cy] = true;
							queue.add(new Point(cx, cy));
						}
					}
				}
			}
			len = queue.size();
		}
	}
   
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		String[] input = br.readLine().split(" ");
      	int size = Integer.parseInt(input[0]);
      	int type = Integer.parseInt(input[1]);
      	virus_points = new ArrayList[type + 1];
      	for(int i = 0; i <= type; i++) {
      		virus_points[i] = new ArrayList<Point>();
      	}
      	map = new int[size][size];
      	visited = new boolean[size][size];
      	for(int i = 0; i < size; i++) {
      		input = br.readLine().split(" ");
      		for(int j = 0; j < size; j++) {
      			map[i][j] = Integer.parseInt(input[j]);
      			if(map[i][j] != 0) {
      				visited[i][j] = true;
      				virus_points[map[i][j]].add(new Point(i, j));
      			}
      		}
      	}
      	input = br.readLine().split(" ");
      	br.close();
      	second = Integer.parseInt(input[0]);
      	int obj_x = Integer.parseInt(input[1]);
      	int obj_y = Integer.parseInt(input[2]);
      	Main m = new Main();
      	m.findVirusType();
      	bw.write(map[obj_x - 1][obj_y - 1] + "\n");
      	bw.flush();
      	bw.close();
	}
   
	static class Point {
		int x, y;
		public Point(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
}

4.  접근

• 해당 문제는 BFS를 이용하여 해결할 수 있습니다.
• BFS 탐색 시에 해당 위치를 탐색했는지 파악하기 위한 2차원 배열 visited를 생성하고 특정한 칸에 바이러스가 이미 존재한다면 다른 바이러스가 들어갈 수 없기 때문에 주어진 시험관 정보에서 바이러스가 존재하는 곳은 visited의 값을 true로 변경하여 탐색하지 않게 합니다.
• 바이러스가 감염된 곳들을 Queue에 넣어 BFS를 통해 이후에 바이러스들이 증식해나가는 과정을 확인합니다.
• 이 때, 1초마다 Queue에 들어있는 데이터의 개수를 확인해서 해당 데이터에 대해서만 증식을 시킨다면 1초마다의 증식된 상태를 확인할 수 있고 이러한 방법을 S초만큼 진행한다면 S초가 지난 후의 바이러스가 증식된 상태를 알 수 있습니다.
• 바이러스는 번호가 낮은 종류의 바이러스부터 증식해나가기 때문에 처음에 Queue에 데이터를 넣을 때, 바이러스의 번호가 낮은 순서대로 넣어준다면 해당 조건에 맞게 증식됩니다.

public void findVirusType() {
	int[] dx = {-1, 0, 1, 0};
	int[] dy = {0, -1, 0, 1};
	Queue<Point> queue = new LinkedList<Point>();
	for(int i = 1; i < virus_points.length; i++) {
		for(int j = 0; j < virus_points[i].size(); j++) {
			queue.add(virus_points[i].get(j));
		}
	}
	int len = queue.size();
	for(int i = 0; i < second; i++) {
		for(int j = 0; j < len; j++) {
			Point cur_point = queue.poll();
			for(int l = 0; l < 4; l++) {
				int cx = cur_point.x + dx[l];
				int cy = cur_point.y + dy[l];
				if(cx >= 0 && cx < map.length && cy >= 0 && cy < map.length) {
					if(!visited[cx][cy] && map[cx][cy] == 0) {
						map[cx][cy] = map[cur_point.x][cur_point.y];
						visited[cx][cy] = true;
						queue.add(new Point(cx, cy));
					}
				}
			}
		}
		len = queue.size();
	}
}

1. 시험관의 x좌표와 y좌표를 멤버 변수로 하는 클래스 Point를 선언하고 처음 시험관 상태에서 바이러스가 있는 위치를 나타내는 1차원 ArrayList 배열 virus_points를 생성합니다.
2. BFS 탐색 시에 해당 위치를 탐색했는지 파악하기 위한 2차원 배열 visited를 생성하고 시험관의 정보를 나타내는 2차원 배열 map을 생성하며 시험관 정보를 map에 넣어줍니다. 이 때, 바이러스가 있는 곳은 visited 값을 true로 변경해주고 해당 위치를 바이러스 종류에 맞게virus_points에 넣어줍니다.
3. BFS를 통해 S초 후의 (X, Y)에 존재하는 바이러스의 종류를 구합니다.
   1. 상하좌우를 나타내는 1차원 배열 dx, dy를 생성합니다.
   2. Queue를 하나 생성하고 번호가 낮은 종류의 바이러스부터 높은 종류의 바이러스 순서대로 Queue에 바이러스가 있는 곳의 위치를 넣어줍니다.
   3. Queue에 들어있는 데이터의 개수를 나타내는 변수 len을 생성하고 현재 Queue에 들어있는 데이터의 개수로 값을 초기화합니다.
   4. S번만큼 반복문을 돌며 S초 후의 바이러스가 증식된 상태를 구합니다.
      1. 1초마다의 바이러스가 증식된 상태를 구하기 위해 len번만큼 반복문을 돌며 1초마다의 바이러스가 증식된 상태를 구합니다.
         1. Queue에서 탐색할 위치를 꺼내서 변수 cur_point에 넣습니다.
         2. cur_point의 상하좌우 위치를 탐색하면서 각 위치에서의 바이러스 증식 여부를 확인합니다.
            1. cur_point에서 이동한 현재 위치의 x좌표와 y좌표를 나타내는 변수 cx, cy를 생성하고 현재 위치의 x좌표와 y좌표로 각각 값을 초기화합니다.
            2. 만약 현재 위치가 시험관 내에 존재하고 아직 바이러스에 감염되지 않았다면
               1. 현재 위치의 값을 cur_point의 값으로 변경하여 바이러스에 증식된 칸임을 나타냅니다.
               2. 현재 위치의 visited 값을 true로 변경합니다.
               3. Queue에 현재 위치를 넣어줍니다.
      2. len의 값을 현재 Queue에 들어있는 데이터의 개수로 변경합니다.
4. 3번의 작업이 모두 끝난 후에 map의 (X, Y)값을 출력합니다.