백준 20652 Stuck in a Rut [C]

문제

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

20652번: Stuck in a Rut

 

문제 해설

소의 마리수 N이 첫줄에 주어지고 소가 위치해있는 x,y 의 좌표와 소가 가고자하는 방향 (E 동쪽 / N 북쪽)이 주어진다. 소는 해당 방향으로 움직이며 해당 좌표에 있는 풀이 다른 소에게 이미 먹혔으면 멈춘다. 두 마리의 소가 동시에 도착하는 경우에는 두 소 모두 먹을 수 있다. 동쪽으로 움직이는 경우 (x, y) -> (x+1,y) 을 움직이는데 1만큼의 시간이 걸리고, 북쪽으로 움직이는 경우 (x,y) -> (x,y+1)을 움직이는데 1만큼의 시간이 걸린다. 각 소의 정보가 주어졌을 때, 해당 소가 몇 시간만큼 움직이는지, 무한대로 움직일 수 있다면 INFINITY를 출력하는 문제이다.

 

예제를 예로 들어 설명하자면, (5,3)에서 북쪽으로 이동하는 2번째 소와 (4,6)에서 동쪽으로 이동하는 3번째 소는 (5,6)에서 만나게된다. 이 때, 2번째소는 (5,6)까지 도달하는데 3의 시간이 걸리고, 3번째 소는 1의 시간이 걸린다. 따라서, 3번째 소가 도착한 이후에 2번째 소가 (5,6)에 도착하게 되어 2번째 소는 (5,6)에서 더이상 진행하지 못하게 된다. 따라서, 2번째 소는 3만큼의 시간동안만 움직일 수 있어 3을 출력하게 된다.

 

풀이

방향이 서로 다를 때에만 교차할 수 있는 점에 착안하여 우선 소들이 움직일 때 만날 수 있는 교차점들을 모두 구해준다. 해당 교차점을 구할 때 어느 소와 어느 소가 교차했는지도 같이 저장해준다. 교차점을 모두 구했다면, 교차한 두 소가 해당 교차점까지 걸린 시간을 구해준다. 시간이 같다면 두 소 모두 이후로 진행 가능하므로 무시해주고, 다르다면 시간이 더 많이 걸린 소에 교차점까지 걸린 시간을 넣어주면 된다.  추가로, 해당 소가 이전 교차점에서 멈추어서 더이상 진행할 수 없는 경우에 대한 처리만 해주면 문제를 풀 수 있다.

 

코드

#include<stdio.h>
#include<algorithm>

#define INF 2100000000
#define LEN 80

struct LIST {
    char dir;
    int x, y;
} input[LEN];

struct INTERSECT {
    int x, y, i, j;
} intersect[LEN * LEN];

bool cmp(INTERSECT a, INTERSECT b) {
    if (a.x == b.x) return a.y < b.y;
    else return a.x < b.x;
}

int N, intersectLen, ans[LEN];

int abc(int x) {
    if (x >= 0) return x;
    return -x;
}

int main() {
    int i, j;
    scanf("%d\n", &N);
    for (i = 0; i < N; i++) {
        scanf("%c %d %d\n", &input[i].dir, &input[i].x, &input[i].y);
        ans[i] = INF;
    }
    for (i = 0; i < N; i++) {
        for (j = i + 1; j < N; j++) {
            if (input[i].dir == input[j].dir) continue;
            if (input[i].dir == 'N') {
                if (input[i].x > input[j].x && input[i].y < input[j].y) {
                    intersect[intersectLen++] = {input[i].x, input[j].y, i, j};
                }
            } else {
                if (input[i].x < input[j].x && input[i].y > input[j].y) {
                    intersect[intersectLen++] = {input[j].x, input[i].y, j, i};
                }
            }
        }
    }
    std::stable_sort(intersect, intersect + intersectLen, cmp);
    for (i = 0; i < intersectLen; i++) {
        int disY = abc(intersect[i].y - input[intersect[i].i].y);
        if (ans[intersect[i].i] != INF) {
            disY = INF;
        }
        int disX = abc(intersect[i].x - input[intersect[i].j].x);
        if (ans[intersect[i].j] != INF) {
            disX = INF;
        }
        if (disX == disY) continue;
        if (disX < disY) {
            if (disY != INF) ans[intersect[i].i] = disY;
        } else {
            if (disX != INF) ans[intersect[i].j] = disX;
        }
    }
    for (i = 0; i < N; i++) {
        if (ans[i] == INF) {
            printf("Infinity\n");
        } else {
            printf("%d\n", ans[i]);
        }
    }
    return 0;
}