백준 - 18405. 경쟁적 전염

Java언어 중 2등을 달성해 좋아서 작성하는 글이다.

 

18405. 경쟁적 전염

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

 

 

문제

 

 

입출력

 

 

설명

N*N 시험관에 1번부터 바이러스가 놓여있고 숫자가 작은 것부터 상하좌우로 증식한다.

S초 후에 (X, Y)에 바이러스가 존재하는지, 그렇다면 어떤 숫자의 바이러스인지를 출력해야 한다.

 

 

접근

N(시험관 크기), K(바이러스 개수), S(흐른 시간) 값의 범위는 아래와 같다.

• N의 범위: 1 ~ 200
• K의 범위: 1 ~ 1,000
• S의 범위: 0 ~ 10,000

모두 범위가 작기에 문제가 원하는 방법은 BFS를 활용하는 것이라고 생각했다.

다만, 입력에서 S, X, Y의 값이 모두 주어지므로 BFS를 활용하지 않는 방법으로 접근했다.

 

과정은 아래와 같다.

1. 숫자, 가로, 세로 정보를 가진 Virus 인스턴스를 생성해 Queue에 담는다.
2. Queue에서 하나씩 빼면서 (X, Y)와의 거리를 계산한다.
3. 아래의 경우가 아니라면 해당 바이러스의 정보를 최솟값으로 업데이트한다.
   - 계산한 거리가 S보다 멀면 넘긴다.
   - 계산한 거리가 최솟값보다 크면 넘긴다.
   - 계산한 거리가 최솟값과 같으면 바이러스 숫자가 크면 넘긴다.

해당 방법으로 풀면 바이러스의 개수에 비례해 while문이 반복하므로 시간복잡도는 O(K)이다.

 

 

풀이 코드

처음엔 Comparable을 활용해 나름 깔끔한 코드를 지향했는데 속도가 약간 느렸다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

	static int N;

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

		Queue<Virus> queue = new ArrayDeque<>();
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		for (int r = 0; r < N; r++) {
			st = new StringTokenizer(br.readLine());
			for (int c = 0; c < N; c++) {
				int current = Integer.parseInt(st.nextToken());
				
				if(current == 0) {
					continue;
				}
				
				queue.add(new Virus(r, c, current));
			}
		}
		
		
		st = new StringTokenizer(br.readLine());
		int t = Integer.parseInt(st.nextToken());
		int r = Integer.parseInt(st.nextToken())-1;
		int c = Integer.parseInt(st.nextToken())-1;
		
		PriorityQueue<Virus> pq = new PriorityQueue<>();
		while(!queue.isEmpty()) {
			Virus virus = queue.poll();
			virus.setDistance(r, c);
			pq.add(virus);
		}
		
		Virus virus = pq.poll();
		if(virus.distance <= t) {
			System.out.println(virus.value);
		} else {
			System.out.println(0);
		}
	}
}


class Virus implements Comparable<Virus> {
	
	int r;
	int c;
	int value;
	int distance;
	
	public Virus(int r, int c, int value) {
		this.r = r;
		this.c = c;
		this.value = value;
	}
	
	void setDistance(int r, int c) {
		distance = Math.abs(r - this.r) + Math.abs(c - this.c);
	}
	
	@Override
	public int compareTo(Virus o) {
		if(distance != o.distance) {
			return distance - o.distance;
		}
		return value - o.value;
	}
}

 

그래서 Comparable을 버리고 대부분의 작업을 main으로 넘겼더니 빠르게 나왔다. 코드는 훨씬 더럽다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

    static int N;

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

        Queue<Virus> queue = new ArrayDeque<>();

        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        for (int r = 0; r < N; r++) {
            st = new StringTokenizer(br.readLine());
            for (int c = 0; c < N; c++) {
                int current = Integer.parseInt(st.nextToken());

                if(current == 0) {
                    continue;
                }

                queue.add(new Virus(r, c, current));
            }
        }


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

        int minDistance = 201;
        int minValue = 1001;
        boolean isExist = false;
        while(!queue.isEmpty()) {
            Virus virus = queue.poll();

            int distance = Math.abs(r - virus.r) + Math.abs(c - virus.c);
            if(distance > t) {
                continue;
            }

            if(distance > minDistance) {
                continue;
            }

            if(distance < minDistance) {
                minDistance = distance;
                minValue = virus.value;
            } else {
                if(minValue > virus.value) {
                    minValue = virus.value;
                }
            }

            isExist = true;

        }

        if(isExist) {
            System.out.print(minValue);
        } else {
            System.out.print(0);
        }
    }
}


class Virus {

    int r;
    int c;
    int value;
    int distance;

    public Virus(int r, int c, int value) {
        this.r = r;
        this.c = c;
        this.value = value;
    }
}