[BOJ] 18405 - 경쟁적 전염 (Java)

알고리즘

• 구현
• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색

1. 문제

2. Idea

• 우선순위 큐 사용
• time 고려
• 1. 시간대가 작은 것 부터 poll
• 2. 시간대가 같을시 작은 바이러스 숫자 poll

3. 풀이

3.1. 변수 선언 및 초기화

• n: 맵의 크기
• k: 초기 바이러스의 종류 수
• map: 맵의 상태를 나타내는 2차원 배열
• visited: 해당 위치의 방문처리를 위한 배열 (true or false)
• s: 시간
• x, y: 찾고자 하는 위치의 좌표

static int n,k,s,x,y;
static int map[][];
static boolean visited[][];
static int dx[]= {0,0,1,-1};
static int dy[] = {1,-1,0,0};

3.2. 우선순위 큐 설정

• 우선순위 큐(pq)를 생성

static PriorityQueue<Node> pq = new PriorityQueue<>();

3.3. map에 입력값 저장 및 방문처리 + 우선순위 큐(pq)에 추가

• 각 행렬 요소 탐색
• 입력값 저장 및 방문처리(true로 설정)
• 초기에 주어진 바이러스의 위치를 방문했다고 표시
  이는 바이러스가 있는 위치에서 BFS를 시작할 때, 해당 위치를 이미 방문한 것으로 간주하여 중복해서 큐에 넣지 않도록 하기 위함

map = new int[n][n];
visited = new boolean[n][n];
for(int i=0; i<n; i++) {
	String[] map_input = br.readLine().split(" ");
		for(int j=0; j<n; j++) {
			map[i][j] = Integer.parseInt(map_input[j]);
			visited[i][j]=true;
			pq.add(new Node(i,j,0,map[i][j])); //현재 위치 (i, j)에 있는 바이러스의 정보를 우선순위 큐에 추가
		}
	}
}

3.4. BFS 수행 및 결과 출력

• BFS 실행 == 바이러스 전파 과정 실행
• 각 바이러스는 큐에 들어가면서 주변의 빈 칸에 전파되고, 해당 위치의 정보가 우선순위 큐에 추가
• 우선순위 큐를 사용하므로 시간이 작은 것부터 처리
• 시간이 같을 경우, 바이러스 번호가 작은 것부터 처리

public static void bfs() {
        while(!pq.isEmpty()) {
            Node a= pq.poll();
            if(a.time>s) {
                // 문제 조건중 주어진 시간대가 넘어가는 경우 처리(0 출력)
                System.out.println(0);
                return;
            }
            if(a.x==x-1 && a.y==y-1 && map[a.x][a.y]!=0) {

                // map[a.x][a.y]==0 : 바이러스가 전염되지 않은 경우 -> 0이 아닐때만 출력
                System.out.println(a.virus_num);
                return;
            }
            for(int i=0; i<4; i++) { // 상,하,좌,우 탐색
            	// 4가지 방향의 새로운 좌표
                int nx = a.x+dx[i];
                int ny =a.y+dy[i];
                if(nx>=0 && ny>=0 && nx<n && ny<n) { // 새로운 좌표가 범위 내에 있는지 확인
                    if(!visited[nx][ny]) { // 방문 여부(false->아직 방문하지 않은 좌표)
                        visited[nx][ny] = true; // 방문 처리
                        map[nx][ny]=a.virus_num; 새로운 좌표에 현재 바이러스의 번호 설정 -> 바이러스 전염
                        // 바이러스가 전염된 새로운 좌표를 pq에 추가
                        // Node 클래스에 새로운 좌표, 시간, 바이러스 정보 저장
                        pq.add(new Node(nx,ny,a.time+1,a.virus_num));
                    }
                }
            }
        }
    }

3.5. Node Class 구현

• 각 위치(x,y)의 정보
• compareTo 메서드로 우선순위 큐(pq)에서 시간이 작은 것부터, 시간이 같을 경우 바이러스 번호가 작은 것부터 처리되도록 구현

public int compareTo(Node o) {
        if(this.time<o.time || this.time>o.time) {
            return this.time-o.time;
            // 시간이 같을때만 바이러스 번호를 빼야 한다.
            // this.time-o.time -> 작은 숫자가 큐에서 return
        }
        else {
            // 시간이 같을때 바이러스번호가 작은것부터 return
            return this.virus_num - o.virus_num;
        }
    }
}

4. 전체코드

package week5;
//Gold_경쟁적 전염 *
import java.util.*;
import java.io.*;

public class BOJ_18405 {
    static int n,k,s,x,y;
    static int map[][];
    static boolean visited[][];
    static int dx[]= {0,0,1,-1};
    static int dy[] = {1,-1,0,0};
    static PriorityQueue<Node> pq = new PriorityQueue<>();
    // 1. 시간대가 작은 것 부터 poll
    // 2. 시간대가 같을시 작은 바이러스 숫자 poll
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] t = br.readLine().split(" ");
        n = Integer.parseInt(t[0]);
        k = Integer.parseInt(t[1]);

        map = new int[n][n];
        visited = new boolean[n][n];
        for(int i=0; i<n; i++) {
            String[] map_input = br.readLine().split(" ");
            for(int j=0; j<n; j++) {
                map[i][j] = Integer.parseInt(map_input[j]);
                if(map[i][j]!=0) {
                    visited[i][j]=true;
                    pq.add(new Node(i,j,0,map[i][j]));
                }
            }
        }

        String[] tt = br.readLine().split(" ");
        s = Integer.parseInt(tt[0]);
        x = Integer.parseInt(tt[1]);
        y = Integer.parseInt(tt[2]);

        bfs();

    }
    public static void bfs() {
        while(!pq.isEmpty()) {
            Node a= pq.poll();
            if(a.time>s) {
                // 문제 조건중 주어진 시간대가 넘어가는 경우 처리(0 출력)
                System.out.println(0);
                return;
            }
            if(a.x==x-1 && a.y==y-1 && map[a.x][a.y]!=0) {

                // map[a.x][a.y]==0 : 바이러스가 전염되지 않은 경우 -> 0이 아닐때만 출력
                System.out.println(a.virus_num);
                return;
            }
            for(int i=0; i<4; i++) {
                int nx = a.x+dx[i];
                int ny =a.y+dy[i];
                if(nx>=0 && ny>=0 && nx<n && ny<n) {
                    if(!visited[nx][ny]) {
                        visited[nx][ny] = true;
                        map[nx][ny]=a.virus_num;
                        pq.add(new Node(nx,ny,a.time+1,a.virus_num));
                    }
                }
            }
        }
    }
}
class Node implements Comparable<Node>{
    int x,y,time,virus_num;
    //time: 바이러스가 퍼질때 걸리는 시간
    //virus_num: 해당 칸에 해당하는 바이러스번호
    Node(int x, int y, int time, int virus_num){
        this.x=x;
        this.y=y;
        this.time=time;
        this.virus_num = virus_num;
    }
    
    public int compareTo(Node o) {
        if(this.time<o.time || this.time>o.time) {
            return this.time-o.time;
            // 시간이 같을때만 바이러스 번호를 빼야 한다.
            // this.time-o.time -> 작은 숫자가 큐에서 return
        }
        else {
            // 시간이 같을때 바이러스번호가 작은것부터 return
            return this.virus_num - o.virus_num;
        }
    }
}