문제출처: www.acmicpc.net/problem/18405
18405번: 경쟁적 전염
첫째 줄에 자연수 N, K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 200, 1 ≤ K ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 시험관의 정보가 주어진다. 각 행은 N개의 원소로 구성되며, 해당 위치
www.acmicpc.net
풀이 과정
- disease객체는 필드를 4개 가진다. 바이러스의 종류(virus), 좌표(row, col), 시간초(s). 여기서 s는 bfs를 진행하면서 해당 바이러스가 몇초 지나고 퍼진 바이러스인지 알려줌.
- 바이러스가 있는 곳을 미리 찾아놓고 Queue에 저장.
- 큐를 virus종류를 기준으로 정렬
- 큐에서 바이러스를 하나씩 꺼내면서 BFS시작.
- BFS과정을 거치면 시간이 1씩 커지면서 바이러스를 퍼뜨린다. 시간(s)이 제한된 시간(S)가 되면 더이상 퍼뜨리지 않는다.
소스코드
package 백준;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;
public class 경쟁적전염_18405 {
static class Disease implements Comparable<Disease> {
int virus;
int row;
int col;
int s;
public Disease(int virus, int row, int col, int s) {
this.virus = virus;
this.row = row;
this.col = col;
this.s = s;
}
@Override
public int compareTo(Disease other) {
return this.virus - other.virus;
}
}
private static int N;
private static int[][] map;
private static int S;
private static int X;
private static int Y;
private static int[] dr = { -1, 1, 0, 0 };
private static int[] dc = { 0, 0, -1, 1 };
private static Queue<Disease> q = new LinkedList<Disease>();
@SuppressWarnings("unchecked")
public static void main(String[] args) throws IOException {
// 데이터 정리
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
st.nextToken(); // K값 안쓴다.
map = new int[N][N];
for (int row = 0; row < N; row++) {
st = new StringTokenizer(br.readLine());
for (int col = 0; col < N; col++) {
int num = Integer.parseInt(st.nextToken());
if (num != 0) {
q.offer(new Disease(num, row, col, 0));
}
map[row][col] = num;
}
}
st = new StringTokenizer(br.readLine());
S = Integer.parseInt(st.nextToken()); // 몇초 = 몇번 퍼지는가
X = Integer.parseInt(st.nextToken()); // 좌표 X
Y = Integer.parseInt(st.nextToken()); // 좌표 Y
// 문제 해결
Collections.sort((List<Disease>) q);
bfs();
// 출력
for (int row = 0; row < N; row++) {
for (int col = 0; col < N; col++) {
sb.append(map[row][col] + " ");
}
sb.append("\n");
}
System.out.println(sb);
// 정달 출력
System.out.println(map[X - 1][Y - 1]);
}
private static void bfs() {
while (!q.isEmpty()) {
Disease disease = q.poll();
if (disease.s == S) {
continue;
}
for (int i = 0; i < 4; i++) {
int tr = disease.row + dr[i];
int tc = disease.col + dc[i];
if (tr >= 0 && tc >= 0 && tr < N && tc < N && map[tr][tc] == 0) {
map[tr][tc] = disease.virus;
q.offer(new Disease(disease.virus, tr, tc, disease.s + 1));
}
}
}
}
}
다른 풀이 방법
package 백준;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;
public class 경쟁적전염2_18405 {
static class Disease implements Comparable<Disease> {
int virus;
int row;
int col;
public Disease(int virus, int row, int col) {
this.virus = virus;
this.row = row;
this.col = col;
}
@Override
public int compareTo(Disease other) {
return this.virus - other.virus;
}
}
private static int N;
private static int[][] map;
private static int S;
private static int X;
private static int Y;
private static int[] dr = { -1, 1, 0, 0 };
private static int[] dc = { 0, 0, -1, 1 };
private static Queue<Disease> q = new LinkedList<Disease>();
@SuppressWarnings("unchecked")
public static void main(String[] args) throws IOException {
// 데이터 정리
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
st.nextToken(); // K값 안쓴다.
map = new int[N][N];
for (int row = 0; row < N; row++) {
st = new StringTokenizer(br.readLine());
for (int col = 0; col < N; col++) {
int num = Integer.parseInt(st.nextToken());
if (num != 0) {
q.offer(new Disease(num, row, col));
}
map[row][col] = num;
}
}
st = new StringTokenizer(br.readLine());
S = Integer.parseInt(st.nextToken()); // 몇초 = 몇번 퍼지는가
X = Integer.parseInt(st.nextToken()); // 좌표 X
Y = Integer.parseInt(st.nextToken()); // 좌표 Y
// 문제 해결
Collections.sort((List<Disease>) q);
bfs();
// 출력
for (int row = 0; row < N; row++) {
for (int col = 0; col < N; col++) {
sb.append(map[row][col] + " ");
}
sb.append("\n");
}
System.out.println(sb);
// 정답 출력
System.out.println(map[X - 1][Y - 1]);
}
private static void bfs() {
while (S-- > 0) { // ex) 시간초가 1이면 1번수행
int virusSize = q.size();
while (virusSize-- > 0) { // ex) 바이러스가 3곳이면 3번 수행
Disease disease = q.poll();
for (int i = 0; i < 4; i++) {
int tr = disease.row + dr[i];
int tc = disease.col + dc[i];
if (tr >= 0 && tc >= 0 && tr < N && tc < N && map[tr][tc] == 0) {
map[tr][tc] = disease.virus;
q.offer(new Disease(disease.virus, tr, tc));
}
}
}
}
}
}
bfs 코드 부분에 집중해보자.
첫 번째로 풀었던 방식은 Disease 클래스에 s필드를 추가하여, 모든 Disease 객체의 s필드에 각각의 시간값을 넣어줬었다. 그리고 모든 큐에 Disease객체를 쌓아 놓고 S와 s값을 비교하여 시간 비교를 했었다.
두 번째 풀이는 S값이 정해져있기 때문에 이를 활용하는 것이다. Disease 객체에서 s값을 빼고, while문에 s-->0 조건을 주어서 주어진 시간동안만 작동하도록한다.
이 코드의 장점은 주어진 시간 S만큼만 루프를 돌면 되기 때문에 S값과 일치하거나 초과하는지 자잘한 s들을 비교할 필요 없고, 객체에 s필드(없어도됨)를 넣어 객체 하나하나에 시간 계산을 안해줘도 되기 때문에 좋다고 생각한다.
비슷한 문제(bfs): ggp03016.tistory.com/11
두번째 풀이 출처: 같은 스터디 성원님.
성원님 tistory 주소: norwayy.tistory.com/