[Java] 백준 18405 경쟁적 전염

문제

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

18405번: 경쟁적 전염

풀이

수학 문제를 풀 때 1 부터 n 까지의 수를 for문을 돌리면서 누적합을 하고 싶은가? 아님 n까지의 수의 합 n*(n+1)/2 으로 한 번에 도출 하겠는가?  당연히 후자일 것이다. 

public int getSum(int n){
        int sum = 0 ;
        for(int i = 1; i < n+1 ;i++)
            sum += i;
        return sum;
}
public int getSum_fast(int n){
        return n*(n+1)/2;
}

getSum() 은 O(N) , getSum_fast는 O(1) 의 시간복잡도를 가진다.

BFS 로 구현한 코드가 많은데,  이 문제의 특징은 1초에 거리 1 만큼 증가하는 것을 볼 수있다.  이 특징을 이용할 것이다. 

 

바이러스의 위치 P1 , 알고싶은 target 위치 P2 의 거리를 구하면 bfs 탐색을 하지 않고 답을 구할 수 있다. 

로직은 다음과 같다.

1. 우선 주어진 map을 탐색해서 map[i][j] > 0 이 되는 바이러스의 위치를 구한다. 
2. 각 바이러스의 위치에서 목표 target (x,y) 까지의 거리를 구한다. 
3. 거리가 S 이하이면 우선순위 큐에 넣는다. 
4. 모든 바이러스를 탐색하고 나면 큐에서 하나 뺴서 답을 도출한다. 
5. 큐 사이즈가 0 이면 0 리턴.

 

내가 푼 로직의 핵심 

두 점의 거리를 수학적으로 구하자!

다음과 같이 두 점 사이의 거리를 수학적으로 구할 수 있따. 

public int getDistance(int sX,int sY, int eX, int eY){
        //start 는 2사분면, end 는 4사분면 으로 정규화.
        if(sX == eX)return Math.abs(sY - eY);
        else if(sY == eY) return Math.abs(sX - eX);
        else{
            if(sX < eX && sY > eY)sY -= (sY - eY)*2;
            else if(sX > eX && sY < eY)sX -= (sX - eX)*2;
        }
        return Math.abs((sX + sY ) - (eX + eY));
    }

 

코드

import java.io.*;
import java.util.*;
public class Main {
    int n,k,s,x,y;
    int [][] map;

    public static void main(String args[]) throws IOException {
        Main m = new Main();
        m.sol();
    }
    public long getN(){
        int ret =0 ;
        // { index, value }
        PriorityQueue<int []> pq = new PriorityQueue<>((a,b)-> a[1]-b[1] == 0 ? a[0]-b[0] : a[1]-b[1]);
        for(int i =0  ;i < n ;i++){
            for(int j= 0  ;j < n ;j++){
                if(map[i][j] > 0){
                    int d = getDistance(i,j,x,y);
                    if(d <= s){
                        pq.offer(new int[]{map[i][j], d});
                    }
                }
            }
        }
        return pq.size()> 0 ? pq.poll()[0] : 0;
    }
    public int getDistance(int sX,int sY, int eX, int eY){
        //start 는 2사분면, end 는 4사분면 으로 정규화.
        if(sX == eX)return Math.abs(sY - eY);
        else if(sY == eY) return Math.abs(sX - eX);
        else{
            if(sX < eX && sY > eY)sY -= (sY - eY)*2;
            else if(sX > eX && sY < eY)sX -= (sX - eX)*2;
        }
        return Math.abs((sX + sY ) - (eX + eY));
    }
    public void sol() throws IOException{
        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++){
                map[i][j]=  Integer.parseInt(st.nextToken());
            }
        }
        st = new StringTokenizer(br.readLine());
        s= Integer.parseInt(st.nextToken());
        x= Integer.parseInt(st.nextToken())-1;
        y = Integer.parseInt(st.nextToken())-1;

        System.out.println(getN());
    }
}