[BJ18405] 경쟁적 전염

🚩 문제 설명

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

18405번: 경쟁적 전염

◾ 바이러스 순서에 따라서 전염이 퍼지고, 특정 인덱스에 해당하는 칸의 바이러스 번호가 무엇인지 출력하는 문제

 

 

 

---

 

 

 

✅ 입출력

변수 설명
N: 바이러스가 들어있는 시험관의 크기
K: 바이러스의 종류 개수
return ➡️ S초 때, 시험관[Y][X] 에 들어있는 바이러스의 번호

✔️ 예제 1

3 2
1 0 0
0 0 0
0 0 2
1 2 3

2

 

 

 

---

 

 

 

📑 문제 풀이

with 자바 (Java)

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;


public class Main {
	static int ans, N, K;
	static int es, ey, ex;
	static int[][] map;

	static List<Virus> list = new ArrayList<>();

	// 상하좌우
	static int[] dy = { -1, 1, 0, 0 };
	static int[] dx = { 0, 0, -1, 1 };


	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		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++) {
				int m = map[i][j] = Integer.parseInt(st.nextToken());
				if (m != 0) list.add(new Virus(i, j, m));
			}

		}

		st = new StringTokenizer(br.readLine());
		es = Integer.parseInt(st.nextToken());
		ey = Integer.parseInt(st.nextToken()) - 1;
		ex = Integer.parseInt(st.nextToken()) - 1;

		Collections.sort(list, (e1, e2) -> e1.k - e2.k);

		// 탐색
		bfs();

		// 출력
		ans = map[ey][ex];
		System.out.println(ans);

	} // end main


	private static void bfs() {
		Queue<Virus> q = new ArrayDeque<>();
		q.addAll(list); // 정렬한 리스트를 큐에 우선 넣는다.

		int dep = 0;
		while (!q.isEmpty()) {
			if (dep == es) return;

			int size = q.size();
			for (int i = 0; i < size; i++) {
				Virus v = q.poll();
				int y = v.y;
				int x = v.x;
				int k = v.k;

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

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

					map[ny][nx] = k;
					q.offer(new Virus(ny, nx, k));
				}

			}

			list.clear();
			list.addAll(q); // 이때까지의 큐를 다시 리스트에 넣어 정렬한다.
			Collections.sort(list, (e1, e2) -> e1.k - e2.k);

			dep++;

		}

	} // end bfs


	static class Virus {
		int y, x;
		int k;


		public Virus(int y, int x, int k) {
			super();
			this.y = y;
			this.x = x;
			this.k = k;
		}


		@Override
		public String toString() {
			return "Virus [y=" + y + ", x=" + x + ", k=" + k + "]";
		}

	} // end Virus
}

💬 Point

➡️  BFS 을 이용하여 바이러스를 전염시킨다.
➡️  바이러스의 번호 순대로 서열을 주기위하여, list 을 이용하여 정렬을 한다.

 

private static void bfs() {
    Queue<Virus> q = new ArrayDeque<>();
    q.addAll(list); // 정렬한 리스트를 큐에 우선 넣는다.

    int dep = 0;
    while (!q.isEmpty()) {
        if (dep == es) return;

        int size = q.size();
        for (int i = 0; i < size; i++) {
            Virus v = q.poll();
            int y = v.y;
            int x = v.x;
            int k = v.k;

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

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

                map[ny][nx] = k;
                q.offer(new Virus(ny, nx, k));
            }

        }

        list.clear();
        list.addAll(q); // 이때까지의 큐를 다시 리스트에 넣어 정렬한다.
        Collections.sort(list, (e1, e2) -> e1.k - e2.k);

        dep++;

    }

} // end bfs

◾ list 에 우선 바이러스 순서대로 정렬을 한다. 번호가 작은 순서대로 정렬이 된다.

◾ 정렬된 list 을 bfs 로 돌리기 위해서 큐에 넣는다.

◾ 한 depth 을 돌면 바이러스가 주변에 전염이 된다.

◾ 하나의 depth 가 끝나면, 해당 큐에 들어있는 바이러스 들을 순서대로 정렬해주기 위해서 list 에 넣는다.

◾ list 에 넣어 정렬을 해주고 위를 반복한다. 만약 depth 가 S와 같다면 메서드를 바로 return 한다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

# 백준 경쟁적 전염 java

# 백준 경쟁적 전염 자바

---