[백준] 18405 경쟁적 전염 - Java

 

 

 

문제 출저

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

18405번: 경쟁적 전염

 

 

 

 

문제 출저

2차원 배열에 바이러스가 숫자로 부여됩니다.

바이러스는 1초에 상하좌우로 퍼지고 이미 바이러스가 있다면 퍼지지 않습니다.

s 초 후, (x,y) 좌표에 어떤 바이러스가 있는지 구해야 합니다. 

 

 

구현으로 문제룰 플었습니다. 

dot 클래스를 만들어 x,y,count 좌표를 만들었습니다.

List<Queue<dot>> virus 자료형을 만들어 바이러스 번호대로 위치를 저장했습니다.

for문으로 초 순서대로 낮은 숫자대로 바이러스가 퍼지는 것을 구현했습니다. 

dot의 count는 초를 나타내는 단위로 doc.count 랑 그 순간의 초인 것만 퍼지도록 계산했습니다.

 

 

 

소스 코드

package baekjoon.backjoon11.day0110.day05;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

/*
경쟁적 전염
https://www.acmicpc.net/problem/18405
 */
public class B18405 {

  static int n, k;
  static int[][] board;
  static int s, x, y;

  static int[] dx = {1,0,-1,0};
  static int[] dy = {0,-1,0,1};


  public static void main(String[] args) throws IOException {

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());
    n = Integer.parseInt(st.nextToken());
    k = Integer.parseInt(st.nextToken());

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

    st = new StringTokenizer(br.readLine());
    s = Integer.parseInt(st.nextToken());
    y = Integer.parseInt(st.nextToken());
    x = Integer.parseInt(st.nextToken());

    List<Queue<dot>> virus = new ArrayList<>();
    for(int i = 0; i <= k; i++) {
      virus.add(new LinkedList<>());
    }

    for(int i = 0; i < n; i++) {
      for(int j = 0; j < n; j++) {
        if(board[i][j] != 0) {
          int number = board[i][j];
          virus.get(number).add(new dot(i, j, 0));
        }
      }
    }

    for(int i = 0; i < s; i++) {
      for(int j = 0; j <= k; j++) {
        Queue<dot> que = virus.get(j);


        while(!que.isEmpty() && que.peek().count == i) {
          dot d = que.poll();
          for(int k = 0; k < 4; k++) {
            int ny = d.y + dy[k];
            int nx = d.x + dx[k];

            if (check(ny, nx)) {
              board[ny][nx] = j;
              que.add(new dot(ny, nx, d.count + 1));
            }
          }
        }
      }
    }

    System.out.println(board[y-1][x-1]);

  }



  public static boolean check(int y, int x) {
    if(y >= 0 && y < n && x >= 0 && x < n && board[y][x] == 0) {
      return true;
    }
    else {
      return false;
    }
  }

  public static class dot {
    int y;
    int x;
    int count;

    dot(int y, int x, int count) {
      this.y = y;
      this.x = x;
      this.count = count;
    }
  }
}