[백준] 2983 개구리 공주

문제 주소 : www.acmicpc.net/problem/2983

2983번: 개구리 공주

문제 확인

 

링크로 연결해서 풀 수 있지만 링크를 사용하는 것 자체가 인덱싱에 비하여 느리므로 그래프 형식으로 인덱스를 저장해서 풀었습니다.

 

풀이

 

개구리는 4방향 (P, P), (-P, -P), (-P, P), (P, -P) 방향으로 점프를 하기 때문에 x, y축에 대하여 식을 새워 다음과 같이 m값으로 나타냅니다.

따라서 점 x, y에서 특정 방향으로 이동하기 위해서는 x, y와 움직일 위치가 같은 m 값을 가지는 식 위에 있어야 합니다.

이를 이용하여 이동 가능한 점들을 미리 그래프로 연결해둔 후 방향 이동을 하면 답을 구할 수 있습니다.

 

그래프를 만들기 위해서는 같은 m값을 가지는 좌표끼리 묶어야 합니다. 이를 위해 Y-X 값, Y+X 값 각각을 기준으로 정렬을 하여 묶어주도록 합니다. 이때 x 혹은 y 값을 같이 넣어 정렬을 해 주어야 같은 식에서 A:D, C:B 방향을 결정해줄 수 있으므로 포함하여 정렬을 합니다. map 혹은 set을 이용하여 풀어도 되지만 둘 다 tree 구조를 만들면서 삽입 위치를 찾는 등의 연산이 필요하여 조금 느릴 수 있습니다.

 

X+Y 값을 기준으로 묶은 배열은 B, C 방향을 결정해 주고 x값이 높으면 B 방향에 위치한 값이므로

graph[index[i+1]][C] = index[i], graph[index[i]][B] = index[i+1] 이 됩니다.

Y-X 값을 기준으로 묶은 배열의 경우

graph[index[i+1]][A] = index[i], graph[index[i]][D] = index[i+1] 이 됩니다.

 

처음 위치부터 이동을 하면서 현재 위치의 식물을 제거해야 하므로 이는 A방향에 있는 식물의 D방향 식물은 현재 식물의 D 방향으로 바꾸어 주어야 합니다.

graph[graph[cur][A]][D] = graph[D] 식으로 정리를 해 줍니다. 다른 방향의 식물들 또한 같이 정리해줍니다.

 

코드

#include <iostream>
#include <algorithm>
 
using namespace std;
typedef struct pir {
    int x, y;
}pir;
typedef struct point {
    int val, x, idx;
    bool operator<(point &t)const {
        if (val != t.val)return val < t.val;
        return x < t.x;
    }
}point;
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
 
    pir input[100000];
    point trans[100000];
    char tmp[100001];
    int n, k;
    cin >> n >> k;
    cin >> tmp;
    for (int i = 0; i < n; ++i)
        cin >> input[i].x >> input[i].y;
 
    int graph[100001][4] = { 0 };
 
    for (int i = 0; i < n; i++)
        trans[i] = { input[i].x + input[i].y, input[i].x, i + 1 };
    sort(trans, trans + n);
    for (int i = 0; i < n - 1; i++) {
        if (trans[i].val == trans[i + 1].val) {
            graph[trans[i].idx][1] = trans[i + 1].idx;
            graph[trans[i + 1].idx][2] = trans[i].idx;
        }
    }
 
    for (int i = 0; i < n; i++)
        trans[i] = { input[i].y - input[i].x, input[i].x, i + 1 };
    sort(trans, trans + n);
    for (int i = 0; i < n - 1; i++) {
        if (trans[i].val == trans[i + 1].val) {
            graph[trans[i].idx][0] = trans[i + 1].idx;
            graph[trans[i + 1].idx][3] = trans[i].idx;
        }
    }
 
    int cur = 1, next;
    for (int i = 0; i < k; i++) {
        if (next = graph[cur][tmp[i] - 'A']) {
            if (graph[cur][0])graph[graph[cur][0]][3] = graph[cur][3];
            if (graph[cur][3])graph[graph[cur][3]][0] = graph[cur][0];
            if (graph[cur][1])graph[graph[cur][1]][2] = graph[cur][2];
            if (graph[cur][2])graph[graph[cur][2]][1] = graph[cur][1];
 
            cur = next;
        }
    }
    cout << input[cur - 1].x << ' ' << input[cur - 1].y;
}