[백준] 18405 - 경쟁적 전염

1. 문제

18405번: 경쟁적 전염

2. 개요

N x N 크기의 시험관이 있고, 1 ~ K번 까지의 바이러스가 시험관 어딘가에 존재할 수 있다.

바이러스는 1초마다 낮은 번호부터 현재 위치에서 상하좌우로 전염된다.

이미 바이러스가 전염된 공간은 다른 바이러스가 전염시키지 못한다.

S초 후에 시험관 X Y 위치에 있는 바이러스의 종류를 알아내는 문제.

3. 풀이 및 코드

3-1. 풀이

입력을 받으며, 바이러스의 종류별로 그 위치들을 저장해둔다.

이후에 관찰 시간이 지나거나, 시험관의 관찰 위치가 채워질 때까지 낮은 바이러스부터 bfs로 전파를 진행시킨다. 모든 바이러스 종류에 대한 전파가 끝났다면 시간을 1초 늘리는 것을 반복한다.

마지막으로 해당 위치의 바이러스 종류를 출력한다.

3-2. Python

import sys
from collections import deque

N, K = map(int, sys.stdin.readline().split())

vd = []
for i in range(K+1):
    vd.append([])

board = []

for i in range(N):
    board.append(list(map(int, sys.stdin.readline().split())))

    for j in range(N):
        if board[i][j] == 0:
            continue
        vd[board[i][j]].append([i,j])

S, X, Y = map(int, sys.stdin.readline().split())

t = 0

dirY, dirX = [-1, 0, 1, 0], [0, -1, 0, 1]

while t < S and board[X-1][Y-1] == 0:
    for v in range(K+1):
        if vd[v] == []:
            continue
        
        q = deque(vd[v])
        tmp = []

        while q:
            now = q.popleft()
            nowY, nowX = now[0], now[1]

            for i in range(4):
                nextY, nextX = nowY + dirY[i], nowX + dirX[i]

                if nextY < 0 or nextY >= N or nextX < 0 or nextX >= N:
                    continue
                if board[nextY][nextX] != 0:
                    continue

                board[nextY][nextX] = v
                tmp.append([nextY, nextX])

        vd[v] = tmp

    t += 1

print(board[X-1][Y-1])

3-3. C#

internal class Program
{
    static string[] input;
    static int[] dirY = new int[] { -1, 0, 1, 0 };
    static int[] dirX = new int[] { 0, -1, 0, 1 };
    static List<List<int[]>> vd = new List<List<int[]>>();
    static int[,] board;

    static void Main(string[] args)
    {
        input = Console.ReadLine().Split();

        int N = int.Parse(input[0]);
        int K = int.Parse(input[1]);

        for (int i = 0; i < K+1; i++)
            vd.Add(new List<int[]>());

        board = new int[N, N];

        for (int i = 0; i < N; i++)
        {
            string[] row = Console.ReadLine().Split();
            for (int j = 0; j < N; j++)
            {
                int tmp = int.Parse(row[j]);
                board[i, j] = tmp;

                if (tmp > 0)
                {
                    vd[tmp].Add(new int[] {i,j});
                }
            }
        }

        input = Console.ReadLine().Split();
        int S = int.Parse(input[0]);
        int X = int.Parse(input[1]);
        int Y = int.Parse(input[2]);

        int t = 0;

        while (t < S && board[X - 1, Y - 1] == 0)
        {
            for (int i = 1; i < K+1; i++)
            {
                if (vd[i].Count == 0)
                    continue;

                Queue<int[]> q = new Queue<int[]>(vd[i]);
                Queue<int[]> tmp = new Queue<int[]>();

                while (q.Count > 0)
                {
                    int[] now = q.Dequeue();
                    int nowY = now[0];
                    int nowX = now[1];

                    for (int j = 0; j < 4; j++)
                    {
                        int nextY = nowY + dirY[j];
                        int nextX = nowX + dirX[j];

                        if (nextY < 0 || nextY >= N || nextX < 0 || nextX >= N)
                            continue;
                        if (board[nextY, nextX] != 0)
                            continue;

                        board[nextY, nextX] = i;
                        tmp.Enqueue(new int[] { nextY, nextX });
                    }
                }

                vd[i] = tmp.ToList();
            }
            t += 1;
        }
        Console.WriteLine(board[X-1, Y-1]);
    }
}