자바

import java.io.*;
import java.util.*;
public class competitive_contagion_18405 {
    static class Block {
        int value;
        int y;
        int x;
        int sec;

        Block(int value, int y, int x, int sec) {
            this.value = value;
            this.y = y;
            this.x = x;
            this.sec = sec;
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        int[][] blocks = new int[N][N];

        for (int i = 0; i < N; i++){
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++){
                int value = Integer.parseInt(st.nextToken());
                blocks[i][j] = value;
            }
        }

        st = new StringTokenizer(br.readLine());
        int S = Integer.parseInt(st.nextToken());
        int X = Integer.parseInt(st.nextToken());
        int Y = Integer.parseInt(st.nextToken());
        boolean[][] visited = new boolean[N][N];

        List<Block> queue = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (blocks[i][j] != 0) {
                    queue.add(new Block(blocks[i][j], i, j, 0));
                    visited[i][j] = true;
                }
            }
        }

        Collections.sort(queue, new Comparator<Block>() {
            @Override
            public int compare(Block b1, Block b2) {
                return b1.value - b2.value;
            }
        });

        int result = bfs(blocks, visited, queue, N, S, X, Y);
        System.out.println(result);
    }

    public static int bfs(int[][] blocks, boolean[][] visited, List<Block> queue, int N, int S, int X, int Y) {
        int[] dy = {-1, 1, 0, 0};
        int[] dx = {0, 0, -1, 1};

        while (!queue.isEmpty()) {
            Block block = queue.remove(0);
            int value = block.value;
            int y = block.y;
            int x = block.x;
            int sec = block.sec;

            if (sec == S) {
                break;
            }

            for(int i = 0; i < 4; i++) {
                int ny = dy[i] + y;
                int nx = dx[i] + x;
                if (ny >= 0 && ny < N && nx >= 0 && nx < N && !visited[ny][nx] && blocks[ny][nx] == 0) {
                    blocks[ny][nx] = value;
                    visited[ny][nx] = true;
                    queue.add(new Block(value, ny, nx, sec + 1));
                }
            }
        }

        return blocks[X-1][Y-1];
    }
}

로직 설명

이 코드는 경쟁적 감염 문제를 해결하는 자바 코드입니다. 문제의 목표는 특정 시간(S) 후에 주어진 위치(X, Y)에 존재하는 바이러스의 종류를 알아내는 것입니다.

이 코드의 주요 로직은 다음과 같습니다:

1. 먼저, 2차원 보드의 크기(N)와 바이러스의 종류(K)를 입력받습니다.

2. 보드의 각 위치에 현재 존재하는 바이러스의 종류를 입력받습니다.

3. 주어진 시간(S) 후에 알고자 하는 위치(X, Y)를 입력받습니다.

4. BFS를 사용하여 바이러스를 전파시킵니다. BFS를 시작하기 전에 초기에 존재하는 모든 바이러스를 큐에 추가하고, 각 바이러스가 보드에서 위치한 좌표와, 바이러스의 종류, 그리고 현재 시간(0초)을 저장합니다. 그 후에 바이러스의 종류를 기준으로 오름차순 정렬하여 작은 번호의 바이러스가 먼저 전파되도록 합니다.

5. BFS 를 진행하면서 큐에서 바이러스를 하나씩 꺼내고, 그 바이러스가 상하좌우로 전파되도록 합니다. 이때, 바이러스가 전파되는 곳이 보드를 벗어나지 않고, 이미 다른 바이러스에 의해 감염되지 않은 곳이어야 합니다. 바이러스가 전파되면 그 위치에 바이러스 종류를 저장하고, 그 위치를 방문했다는 것을 표시합니다. 그리고 현재 시간에 1을 더한 후 큐에 추가합니다.

6. 만약 현재 시간이 주어진 시간(S)과 같아지면 BFS를 종료합니다.

7. 마지막으로 주어진 위치(X, Y)에 존재하는 바이러스의 종류를 반환합니다.

이 알고리즘은 BFS를 이용하여 바이러스가 전파되는 과정을 시뮬레이션하며, 이를 통해 주어진 시간 후에 특정 위치에 어떤 바이러스가 존재하는지 알아냅니다.

노드

const fs = require("fs");
const stdin = process.platform === "linux" ? fs.readFileSync("/dev/stdin").toString().trim() : fs.readFileSync("input.txt").toString().trim();

const input = stdin.split("\n");
let idx = 0;

const [N, K] = input[idx++].split(" ").map(Number);
const blocks = [];
for (let i = 0; i < N; i++) {
  blocks.push(input[idx++].split(" ").map(Number));
}

const [S, X, Y] = input[idx++].split(" ").map(Number);
const visited = Array.from(Array(N), () => Array(N).fill(false));

const queue = [];
for (let i = 0; i < N; i++) {
  for (let j = 0; j < N; j++) {
    if (blocks[i][j] !== 0) {
      queue.push([blocks[i][j], i, j, 0]);
      visited[i][j] = true;
    }
  }
}

queue.sort((a, b) => a[0] - b[0]);

const result = bfs(blocks, visited, queue, S, N, X, Y);
console.log(result);

function bfs(blocks, visited, queue, S, N, X, Y) {
  const dy = [-1, 1, 0, 0];
  const dx = [0, 0, -1, 1];

  while (queue.length > 0) {
    const [value, y, x, sec] = queue.shift();

    if (sec === S) {
      break;
    }

    for (let d = 0; d < 4; d++) {
      const ny = dy[d] + y;
      const nx = dx[d] + x;
      if (ny >= 0 && ny < N && nx >= 0 && nx < N && !visited[ny][nx] && blocks[ny][nx] === 0) {
        blocks[ny][nx] = value;
        visited[ny][nx] = true;
        queue.push([value, ny, nx, sec + 1]);
      }
    }
  }

  return blocks[X - 1][Y - 1];
}

파이썬

def bfs(blocks, visited, queue, S, N, X, Y):
    dy = [-1, 1, 0, 0]
    dx = [0, 0, -1, 1]
    
    while queue:
        value, y, x, sec = queue.pop(0)
        
        if sec == S: 
            break
        
        for d in range(4):
            ny = dy[d] + y
            nx = dx[d] + x
            if 0 <= ny < N and 0 <= nx < N and not visited[ny][nx] and blocks[ny][nx] == 0:
                blocks[ny][nx] = value
                visited[ny][nx] = True
                queue.append((value, ny, nx, sec+1))
    
    return blocks[X-1][Y-1]
        
N, K = map(int, input().split())
blocks = [list(map(int, input().split())) for _ in range(N)]
S, X, Y = map(int, input().split())
visited = [[False] * N for _ in range(N)]

queue = []
for i in range(N):
    for j in range(N):
        if blocks[i][j] != 0:
            queue.append((blocks[i][j], i, j, 0))
            visited[i][j] = True
            
queue.sort()
result = bfs(blocks, visited, queue, S, N, X, Y)
print(result)