[백준] 알고리즘 분류(구현,JAVA)18405번, 경쟁적 전염

문제 링크

18405번: 경쟁적 전염

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에 핵심

 

1. 바이러스 번호가 낮은 것부터 전염이 시작됩니다.

2. 바이러스는 상하좌우 인접한 바이러스가 전염되지 않는 칸으로 전염됩니다.

3. S초가 지난 뒤 (X, Y)의 칸의 정보를 결과로 출력합니다.

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. S초가 될 때까지 바이러스 전염을 진행합니다.

 

3. (X, Y)칸에 정보를 결과로 출력합니다.

 

 

바이러스 전염

 

바이러스는 상하좌우 인접한 바이러스 전염되지 않는 구역이 전염됩니다.

 

상하좌우를 탐색하기 위해서 좌표를 변경해주는 배열을 사용하였습니다.

 

dx[] = {0, 0, -1, 1} : x값을 상하좌우 변경해주는 값

dy[] = {-1, 1, 0, 0} : y값을 상하좌우 변경해주는 값

 

전염되지 않은 구역 : 0

 

바이러스 번호가 낮은 것부터 상하좌우를 탐색하여 전염을 진행합니다.

 

문제를 이해하시려면 예제가 진행되는 과정을 살펴보시는 것이 쉽습니다.

 

예제입력 2.

 

1. 입력된 정보를 저장합니다.

 

N : 3

K : 3

 

시험관 정보

 

1	0	2
0	0	0
3	0	0

 

S : 1

X : 2

Y : 2

 

2. S초가 될 때까지 바이러스 전염을 진행합니다.

 

바이러스 전염 진행!

 

1초.

 

바이러스 1번 전염 진행!

 

1	1	2
1	0	0
3	0	0

 

바이러스 2번 전염 진행!

 

1	1	2
1	0	2
3	0	0

 

바이러스 3번 전염 진행!

 

1	1	2
1	0	2
3	3	0

 

3. (X, Y)칸에 정보를 결과로 출력합니다.

 

 

현재 시험관

1	1	2
1	0	2
3	3	0

 

(X , Y) = (2, 2) = 0

 

0을 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer를 이용하여 시험관의 정보들을 띄어쓰기 기준 나누었습니다.
• S초동안 1번 바이러스부터 순서대로 전염을 진행합니다.
• (X, Y) 좌표의 시험관 정보를 결과로 BufferedWriter에 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• inSpace함수는 이동하려는 좌표가 시험관에 존재하는지 확인합니다.

 

결과코드

import java.util.*;
import java.io.*;

public class Main {
    //위치 관련 클래스
    static class position{
        int x, y;
        public position(int x, int y){
            this.x = x;
            this.y = y;
        }
    }
    static int[][] map;	//시험관 정보 저장 배열
    static Queue<position>[] viruses;	//각 번호 바이러스들 위치 저장 Queue
    static int[] dx = {0, 0, -1, 1};	//상하좌우 x변경값
    static int[] dy = {-1, 1, 0, 0};	//상하좌우 y변경값
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        map = new int[N+1][N+1];
        viruses = new LinkedList[K+1];
        for(int i=0;i<=K;i++)
            viruses[i] = new LinkedList<>();
        //시험관 정보 및 바이러스 저장
        for(int i=1;i<=N;i++){
            st = new StringTokenizer(br.readLine()," ");
            for(int j=1;j<=N;j++){
                map[i][j] = Integer.parseInt(st.nextToken());
                viruses[map[i][j]].add(new position(j, i));
            }
        }
        st = new StringTokenizer(br.readLine()," ");
        int S = Integer.parseInt(st.nextToken());
        int X = Integer.parseInt(st.nextToken());
        int Y = Integer.parseInt(st.nextToken());
        //S초 전염 시작
        for(int i=0;i<S;i++){
            for(int j=1;j<=K;j++){	//1~K번 바이러스 탐색
                int size = viruses[j].size();
                for(int s=0;s<size;s++){
                    position cur = viruses[j].poll();
                    //인접한 칸 탐색
                    for(int t=0;t<4;t++){
                        int tempX = cur.x + dx[t];
                        int tempY = cur.y + dy[t];
                        if(inSpace(tempX,tempY,N) && map[tempY][tempX]==0){
                            map[tempY][tempX] = j;
                            viruses[j].add(new position(tempX,tempY));
                        }
                    }
                }
            }
        }
        bw.write(map[X][Y] + "");	//(X, Y)의 정보 BufferedWriter 저장
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //이동하려는 좌표가 시험관에 존재하는지 확인하는 함수
    static boolean inSpace(int x, int y, int N){
        //시험관에  존재할 때
        if(x > 0 && y> 0 && x<=N && y<=N)
            return true;
        return false;
    }
}