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

[ 백준 ] 경쟁적 전염 18405- JAVA 문제풀이

문제설명

 

생각해야할 요소

1. 생각해줘야 할 포인트는 바이러스 번호가 낮은 숫자부터 시작하고 덮어쓰기가 안된다는 것이다. 

cf) BFS 문제인가? 맨처음 문제를 봤을 때 BFS라고 생각했지만, 문제를 풀다보니까 맞나? 싶기도 하고... 

 

 

문제풀이 방법

1.사실 무척 간단하다. map을 순회하면서 내가 전이할 virus의 번호와 일치하는 것을 Queue에 몽땅 집어 넣어준다.

  - 큐에 들어있는 값의 상하좌우를 보고, map의 범위에 벗어나는것, 이미 그 칸을 점령하고 있는 바이러스가 있을 경우를 제외해주고 virus를 넣어주면 된다. 

 

2. 시간이 오래 걸리지 않기 위해서 X,Y 위치에 값이 0이 아니라면 루프를 빠져나갈 수 있도록 했다.

 

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class CompetitiveContagion_18405 {

    static int N;

    static int[][] map;
    static int[] dx = {1,-1,0,0};
    static int[] dy = {0,0,1,-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());
        int K = Integer.parseInt(st.nextToken());

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

        st = new StringTokenizer(br.readLine());
        int S = Integer.parseInt(st.nextToken());
        int X = Integer.parseInt(st.nextToken())-1;
        int Y = Integer.parseInt(st.nextToken())-1;

        loop:
        for(int i=0; i<S; i++) {
            for(int j=0; j<K; j++) {
                BFS(j+1);

                if(map[X][Y] != 0) break loop;
            }
        }

        System.out.println(map[X][Y]);
    }

    public static void BFS(int virus) {
        Queue<Pair> queue = new LinkedList<>();

        for(int i=0; i<N; i++) {
            for(int j=0; j<N; j++) {
                if(map[i][j] == virus) queue.add(new Pair(i, j));
            }
        }

        while (!queue.isEmpty()) {
            Pair qu = queue.poll();

            for(int k=0; k<4; k++) {
                int nx = qu.x + dx[k];
                int ny = qu.y + dy[k];

                if(nx < 0 || nx >= N || ny < 0 || ny >= N ) continue;
                if(map[nx][ny] != 0) continue;

                map[nx][ny] = virus;
            }
        }
    }

    static class Pair {
        int x,y;

        public Pair(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}

 

 

문제링크

www.acmicpc.net/problem/18405

18405번: 경쟁적 전염