BOJ) 생물학자 (3116 번)

생물학자

3116번: 생물학자

수학 문제라고 느껴졌다.

박테리아의 위치가 주어지고, 방향이 주어진다.

아래의 방향에 따라서, 매 초 일정하게 이동을 할 때, 박테리아 여러 마리가 같은 칸에 제일 많이 있을 때가 언제인지, 그리고 그 때 몇 마리가 같은 칸에 있었는지 구하는 문제였다.

또한, X값은 왼쪽에서 오른쪽으로 갈 수록 증가하며, Y값은 위로 갈수록 증가한다는 조건이 있다.

즉, 1번은 매초 X값이 -1씩, Y값이 +1씩 변화하는 방향이다.

 

풀이

먼저, 박테리아가 만나는지 판단을 해주어야 했다.

getMeetTime이라는 메소드를 만들어서 만나는 시간을 판별했다.

주어진 예시로 살펴보면 (1,1)에서 방향 1인 박테리아는 3초 후, (1,7)에서 방향 7인 박테리아와 만난다.

이를 수식으로 세워보면

편의상 1번 박테리아, 7번 박테리아라고 하겠다. (방향)

 

1번 박테리아는

x = 1 + t * -1   ,   y = 1 + t * 1  이라는 식을 갖는다. t는 시간을 의미한다.(초)

 

7번 박테리아는

x = 1 + t * -1   ,   y = 7 + t * -1 이라는 식을 갖는다.

 

이 두 박테리아가 만나는 시간을 살펴보자.

	1번 박테리아	7번 박테리아	식	결과
x축	1 - t	1 - t	1 -t = 1 -t	t =0
y축	1 + t	7 -t	1 +t = 7 -t	t =3

x의 위치가 서로 같고, 방향이 같기때문에 t=0이라는 결과가 나온다.

y는 3초 후 같은 위치에서 만남을 알 수 있다.

 

 

그럼 만나지 않는 박테리아는 어떨까??

 

위의 1번 박테리아와 (-6,0)에서 방향 3인 3번 박테리아를 살펴보자

	1번 박테리아	3번 박테리아	식	결과
x축	1 - t	6 - t	1 - t =  6 - t	t = 3.5
y축	1 + t	0 + t	1 + t = 0 + t	t = 0

y는 같은 방향으로 움직여서 t =0 이라는 결과가 나오지만, 만날 수 없다.

x축은 t =3.5라는 결과가 나오는데, x축에서 칸 안에 만날 수 없음을 의미한다. (칸 이동하다가 잠시 좌표가 같을 수 있겠지만, 만나지는 않는다.)

 

위와 같은 예외 상황들을 생각하면서 예외 처리와 식을 세워 아래의 코드를 작성했다.

 

코드

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Biologist_3116 {
    static final int[] dx = {0,-1,0,1,1,1,0,-1,-1}, dy = {0,1,1,1,0,-1,-1,-1,0};
    static final int NO_MEETING = 0, DEFAULT_COUNT =2, MAX_TIME = 2000001;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine().trim());
        Bacteria[] bacteriaArr = new Bacteria[n];

        for(int i=0; i<n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine().trim());
            bacteriaArr[i] = new Bacteria(Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken()));
        }

        br.close();
        solution(n, bacteriaArr);
    }

    private static void solution(int n, Bacteria[] bacteriaArr) {
        // 만나는지 검사
        int[] answerArr = inspection(n,bacteriaArr);
        // print
        printAnswer(answerArr);
    }

    private static int[] inspection(int n, Bacteria[] bacteriaArr) {
        int[] groups = new int[MAX_TIME];
        int[] counts = new int[MAX_TIME];
        int groupNum =0;
        int[] answer = new int[2];

        for(int i=0; i<n; i++) {
            groupNum++;
            for(int j=i; j<n; j++) {
                int time = getMeetTime(bacteriaArr[i],bacteriaArr[j]);
                if(time ==NO_MEETING) {
                    continue;
                }
                if (groups[time] != groupNum ) {
                    groups[time] = groupNum;
                    counts[time] =DEFAULT_COUNT;
                } else {
                    counts[time]++;
                }
                if(isChangeAnswer(counts, answer, time)) {
                    answer[0] = counts[time];
                    answer[1] = time;
                }
            }
        }

        return answer;
    }
    private static boolean isChangeAnswer(int[] counts, int[] answer, int time) {
        return counts[time] > answer[0] || (counts[time] == answer[0] && time < answer[1]);
    }

    private static int getMeetTime(Bacteria origin, Bacteria target) {
        int x=NO_MEETING;  // x가 만나는 시간, 0 인 경우는 언제든 만남
        int y=NO_MEETING;  // x가 만나는 시간, 0 인 경우는 언제든 만남

        int xDiv = dx[target.direction] - dx[origin.direction];
        int yDiv = dy[target.direction] - dy[origin.direction];

        if(xDiv !=0) {
            int xMod = (origin.x - target.x) % xDiv;
            x = xMod ==0 ? (origin.x - target.x) / xDiv : NO_MEETING;
        }
        if(yDiv !=0) {
            int yMod = (origin.y - target.y) % yDiv;
            y = yMod ==0 ? (origin.y - target.y) / yDiv : NO_MEETING;
        }

        if(x==0 && y==0) { // 만나지 못하는 경우 ~> 같은 방향
            return NO_MEETING;
        } else if(x <0 || y<0) { // 서로 다른 방향으로 진행할 경우
            return NO_MEETING;
        }
        int time = Math.max(x,y); // x == y or 0,y 초 or x,0 초에 만남

        return (origin.x + dx[origin.direction]*time == target.x + dx[target.direction]*time) &&
                (origin.y + dy[origin.direction]*time == target.y + dy[target.direction]*time) ?
                time : NO_MEETING;
    }

    private static void printAnswer(int[] answerArr) {
        StringBuilder sb = new StringBuilder();
        sb.append(answerArr[0]).append("\n").append(answerArr[1]);
        System.out.println(sb.toString());
    }

    private static class Bacteria {
        int x,y,direction;

        public Bacteria(int x, int y, int direction) {
            this.x = x;
            this.y = y;
            this.direction = direction;
        }
    }
}