[ 백준 ] 18405 경쟁적 전염

📌 Problem

• N x N 크기의 시험관에 바이러스들을 배양한다.
• 바이러스는 1 ~ K의 정수로 이루어져 있다.
• 바이러스는 매초 상하좌우로 증식한다.
• 증식은 낮은 번호의 바이러스부터 진행된다.
• 이미 바이러스가 증식된 칸으로는 새로운 바이러스가 침투할 수 없다.
• S초가 지난 후에 X, Y에 증식된 바이러스 번호를 구한다. (없으면 0)

📌 Solution

매초마다 바이러스들을 증식시키고 S초 이후의 X, Y에 있는 바이러스 번호를 출력하면된다. 한 번 증식된 바이러스는 다른 바이러스가 침투할 수 없기 때문에 X, Y에 바이러스가 증식했다면 추가 증식을 종료해도 된다.

for (int row = 0; row < tube.length; row++)
    for (int col = 0; col < tube.length; col++)
        if (tube[row][col] > 0) proliferation(row, col);

다만, 작은 번호의 바이러스부터 증식을 하는데 이를 순서대로 진행하기는 어렵다. 때문에 증식을 할 때 음수로 증식을 한 후 더 작은 번호가 같은 칸에 증식이 된다면 새로운 번호로 증식한다. 예를 들어 (2, 3) 칸에 3번 바이러스가 증식을 했다면 해당 칸을 -3으로 한다. 이후 2번 바이러스가 동일한 칸에 증식한다면 -2으로 변경한다.

for (int m = 0; m < 4; m++) {
    try {
        int virus = tube[row + moves[m][0]][col + moves[m][1]];
        if (virus == 0 || (virus < 0 && -virus > tube[row][col]))
            tube[row + moves[m][0]][col + moves[m][1]] = -tube[row][col];
    } catch (ArrayIndexOutOfBoundsException ignore) {
    }
}

1초가 지난 후에는 음수들을 양수로 바꾼다.

for (int row = 0; row < tube.length; row++)
    for (int col = 0; col < tube.length; col++)
        tube[row][col] = Math.abs(tube[row][col]);

증식을 하다가 원하는 칸에 바이러스가 증식했다면 종료한다.

while (time-- > 0 && virus == 0) {
    testTube.proliferation();
    virus = testTube.searchVirus(targetRow, targetCol);
}

📌 Code

StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
int size = Integer.parseInt(tokenizer.nextToken());
TestTube testTube = new TestTube(size);

for (int row = 0; row < size; row++) {
    tokenizer = new StringTokenizer(reader.readLine());
    for (int col = 0; col < size; col++)
        testTube.addVirus(row, col, Integer.parseInt(tokenizer.nextToken()));
}

tokenizer = new StringTokenizer(reader.readLine());
int time = Integer.parseInt(tokenizer.nextToken());
int targetRow = Integer.parseInt(tokenizer.nextToken()) - 1;
int targetCol = Integer.parseInt(tokenizer.nextToken()) - 1;

int virus = testTube.searchVirus(targetRow, targetCol);
while (time-- > 0 && virus == 0) {
    testTube.proliferation();
    virus = testTube.searchVirus(targetRow, targetCol);
}
result.append(virus);

class TestTube {

    private final int[][] tube;

    public TestTube(int size) {
        tube = new int[size][size];
    }

    public void addVirus(int row, int col, int virus) {
        tube[row][col] = virus;
    }

    public void proliferation() {
        for (int row = 0; row < tube.length; row++)
            for (int col = 0; col < tube.length; col++)
                if (tube[row][col] > 0) proliferation(row, col);
        for (int row = 0; row < tube.length; row++)
            for (int col = 0; col < tube.length; col++)
                tube[row][col] = Math.abs(tube[row][col]);
    }

    private void proliferation(int row, int col) {
        for (int m = 0; m < 4; m++) {
            try {
                int virus = tube[row + moves[m][0]][col + moves[m][1]];
                if (virus == 0 || (virus < 0 && -virus > tube[row][col]))
                    tube[row + moves[m][0]][col + moves[m][1]] = -tube[row][col];
            } catch (ArrayIndexOutOfBoundsException ignore) {
            }
        }
    }

    public int searchVirus(int row, int col) {
        return tube[row][col];
    }
}