백준 18405 (경쟁적 전염) java

문제

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

18405번: 경쟁적 전염

코드

import java.util.*;
import java.io.*;
import java.awt.Point;
public class Main {
    static int n = 0;
    static int m = 0;
    static int[][] board = new int[201][201];
    static int[][] visit =  new int[201][201];
    static int[] dx = {0,0,-1,1};
    static int[] dy = {1,-1,0,0};
    static int day = 0;
    static int lx = 0;
    static int ly =0;
    static Queue<pair> q =new LinkedList<>();
    public static void main(String[] args) throws Exception {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine()," ");
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        for(int i=1;i<=n;i++)
        {
            st = new StringTokenizer(bf.readLine()," ");
            for(int j=1;j<=n;j++)
            {
                board[i][j]= Integer.parseInt(st.nextToken());
                if(board[i][j]>=1) {
                    visit[i][j] = 1;
                    q.add(new pair(i,j));
                }
            }
        }

        st = new StringTokenizer(bf.readLine()," ");
        day = Integer.parseInt(st.nextToken());
        lx =Integer.parseInt(st.nextToken());
        ly =Integer.parseInt(st.nextToken());

        int start =1;

        for(int k=1;k<=day;k++) {
                bfs(start);
                start = start +1;
            } // 매 초마다 bfs 수행

        System.out.println(board[lx][ly]);
        bf.close();
    }

    static void bfs(int hour) {
       Queue<pair> sub =new LinkedList<>();
       while(!q.isEmpty())
       {
           pair cur = q.poll();
           for(int i=0;i<4;i++)
           {
               int nx = cur.x+dx[i];
               int ny = cur.y+dy[i];

               if(nx>=1&&nx<=n&&ny>=1&&ny<=n)
               {
                   if(visit[nx][ny]==0&&board[nx][ny]==0)
                   {
                       board[nx][ny]=board[cur.x][cur.y];
                       visit[nx][ny]=hour+1;
                       sub.add(new pair(nx,ny));
                   } // 방문한적이 없는 좌표일 경우 

                   else if(visit[nx][ny]==hour+1&&board[nx][ny]>board[cur.x][cur.y])
                   {
                       board[nx][ny]=board[cur.x][cur.y];
                   } // 해당 시간에 방문했지만 값이 더 작은 경우 값을 바꿔야 한다
               }
           }
       }
       q= new LinkedList<>(sub);
    }
}
class pair
{
    int x;
    int y;
    pair(int x, int y)
    {
        this.x =x;
        this.y = y;
    }
}

 

1. 방문한적이 없는 경우 방문 값을 해당 시간의 +1로 설정한다. 그 이유는 다음 탐색에서는 현재 시간 + 1 지점의 값들이 진행될 것이기 때문이다.

2. sub는 다음 탐색에 필요한 좌표값들을 넣어주기 위한 서브 큐이다.

3. 해당 시간에 방문했지만 문제의 조건에서 더 적은 수의 값이 우선순위가 크기 때문에 해당 경우를 고려해준다.