[Gold5] No.18405 경쟁적 전염
28 Apr 2022경쟁적 전염
문제
NxN 크기의 시험관이 있다. 시험관은 1x1 크기의 칸으로 나누어지며, 특정한 위치에는 바이러스가 존재할 수 있다. 모든 바이러스는 1번부터 K번까지의 바이러스 종류 중 하나에 속한다.
시험관에 존재하는 모든 바이러스는 1초마다 상, 하, 좌, 우의 방향으로 증식해 나간다. 단, 매 초마다 번호가 낮은 종류의 바이러스부터 먼저 증식한다. 또한 증식 과정에서 특정한 칸에 이미 어떠한 바이러스가 존재한다면, 그 곳에는 다른 바이러스가 들어갈 수 없다.
시험관의 크기와 바이러스의 위치 정보가 주어졌을 때, S초가 지난 후에 (X,Y)에 존재하는 바이러스의 종류를 출력하는 프로그램을 작성하시오. 만약 S초가 지난 후에 해당 위치에 바이러스가 존재하지 않는다면, 0을 출력한다. 이 때 X와 Y는 각각 행과 열의 위치를 의미하며, 시험관의 가장 왼쪽 위에 해당하는 곳은 (1,1)에 해당한다.
예를 들어 다음과 같이 3x3 크기의 시험관이 있다고 하자. 서로 다른 1번, 2번, 3번 바이러스가 각각 (1,1), (1,3), (3,1)에 위치해 있다. 이 때 2초가 지난 뒤에 (3,2)에 존재하는 바이러스의 종류를 계산해보자.
1초가 지난 후에 시험관의 상태는 다음과 같다.
2초가 지난 후에 시험관의 상태는 다음과 같다.
결과적으로 2초가 지난 뒤에 (3,2)에 존재하는 바이러스의 종류는 3번 바이러스다. 따라서 3을 출력하면 정답이다.
문제풀이
해당 문제는 두가지 방식으로 풀었다. bfs를 이용해 문제를 풀던중 시간 초과로 인해 고생을 하다가. 알아낸 방법들이다.
1. 중첩 반복문 이름을 붙여 시간 초과 회피
첫번째로 반복문에 이름을 붙여 중첩 반복문을 빠져나가 소요시간을 줄인다.
기존의 bfs와 동일하지만 아래의 소스가 살짝 달라진다.
loop:
while(s-- > 0) {
for (int virus = 1; virus <= k; virus++) {
infection(virus);
if (examiner[x-1][y-1] != 0) break loop;
}
}
특별히 설명할 것은 없다. 중첩 반복문에 대해 loop라는 이름을 부여하고 예외 조건일시 해당 모든 반복문을 break한다.
2. 우선 순위 큐를 이용한 풀이 방법
우선 순위 큐는 기존 Queue의 자료구조의 특징인 FIFO을 가지면서, 데이터가 들어온 순서대로 데이터가 나가는 것이 아니라, 우선순위를 먼저 결정 하고 그 우선 순위가 높은 데이터가 먼저 나가는 자료구조이다.
먼저 우선순위 큐를 사용하기 위해서는 아래의 객체를 호출 해야한다.
PriorityQueue<Node> queue = new PriorityQueue<>();
그리고 해당 제네릭 객체인 Node 클래스에서 Comparable를 상속받아 구현해야 한다.
static class Node implements Comparable<Node> {
int y;
int x;
int virus;
int time;
public Node(int y, int x, int virus, int time) {
this.y = y;
this.x = x;
this.virus = virus;
this.time = time;
}
@Override
public int compareTo(Node other) {
if (time == other.time) {
return virus - other.virus;
} else {
return time - other.time;
}
}
}
compareTo 메서드는 문제의 조건에 맞게, 동일한 시간대일 경우에는 숫자가 낮은 바이러스를 먼저 queue.poll() 하도록 구현했다.
또한, 시간이 맞지 않아 1초후의 바이러스 객체와 2초후의 바이러스 객체를 비교할 시 1초후의 바이러스가 먼저 queue.poll()되도록 구현되어 있다.
정리하자면,
- 시간이 같을경우 바이러스의 숫자가 적은 순서
- 시간이 다를경우 시간이 적은 순서
의 순으로 Queue에서 poll을 하여 bfs를 진행해 주면 된다.