[백준 C++] 3089 네잎 클로버를 찾아서

문제

숭이는 지구에 놀러온 외계인에게 조정당하고 있다. 외계인은 숭이를 이용해서 네잎 클로버를 찾은 뒤, 숭이를 그 자리에 놔두고 다시 자기들의 행성으로 떠나려고 한다. 숭이가 있는 곳은 2차원 평면으로 나타낼 수 있고, 클로버는 N개의 점으로 나타나 있다.

숭이의 절친한 친구인 희웅이와 태완이는 숭이를 찾아 다시 정신을 차리게 해주려고 한다. 숭이는 맨 처음에 (0, 0)에 있고, 외계인은 그에게 명령을 M번 전송한다. 각 명령은 네 방향 중 하나이며, 숭이는 그 방향으로 가장 가까운 네잎 클로버가 있는 곳까지 걸어간다.

네잎 클로버의 위치와 외계인이 전송한 명령이 주어졌을 때, 모든 명령을 수행한 뒤에 숭이가 있는 곳의 위치를 찾는 프로그램을 작성하시오.

입력

첫째 줄에 네잎 클로버의 개수 N과 외계인이 전송한 명령의 수 M이 주어진다. (3 ≤ N ≤ 100,000, 1 ≤ M ≤ 100,000)

다음 N개 줄에는 네잎 클로버의 위치 Xi, Yi가 주어진다. (-100,000 < Xi, Yi < 100,000) 한 위치에 두 개 이상의 네잎 클로버가 있는 경우는 없다.

마지막 줄에는 외계인이 숭이에게 내린 명령이 주어진다. 왼쪽 방향은 L, 오른쪽은 R, 위는 U, 아래는 D로 주어진다. 항상 주어지는 방향에는 네잎 클로버가 있다.

출력

숭이의 마지막 위치를 출력한다.

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

풀이

2차원 배열로 문제를 풀려고하면 매번 x, y둘다 체크해야해서 비효율적인데
x, y좌표를 따로 분리한다면 더 쉽게 문제를 풀 수 있다.
이때 분리하는 개념은 동일 x좌표일때의 네잎클로버가있는 위치 y를 배열로 나타내는것이다.
list_x[x][0] = y1 ,list_x[x][1] = y2, list_x[x][2] = y3, ''', list[x][i] = yn 인것.
이러면 예로들어 명령이 위, 아래인경우,
list_x[현재x좌표].size()만큼 순회하여 가장 가까운 좌표를 쉽게 찾아 낼 수있다.

또한, 가장 가까운 좌표를 쉽게 찾기위해, vector로 list_x, list_y를 구현한뒤 sort하여 바로 위, 아래 좌표로 접근할수있도록하였다. 그리고 음의좌표값을 구현하기위해 입력받을때 모든 좌표에 10만을 더하고,

결과를 출력할때 10만을 빼서 출력하였다.

#define _CRT_SECURE_NO_WARNINGS 
#define MAX 100000
#include <bits/stdc++.h>
using std::vector; using std::sort;
//모든 좌표값에 10만을 더하여 0 <= x,y <= 20000 으로 계산
int n, m;
vector<int> list_x[2 * MAX]; //동일한 x좌표만을 나열했을때 각각의 y좌표들
vector<int> list_y[2 * MAX]; //마찬가지
void init() {
    scanf("%d%d", &n, &m);
    for (int i = 0, x, y; i < n; i++) {
        scanf("%d%d", &x, &y);
        list_x[x + MAX].push_back(y + MAX);
        list_y[y + MAX].push_back(x + MAX);
    }
    
    for (int i = 0; i < 2 * MAX; i++) {
        if (list_x[i].size() > 0) sort(list_x[i].begin(), list_x[i].end());
        if (list_y[i].size() > 0) sort(list_y[i].begin(), list_y[i].end());
    }
}

void func() {
    //현재 위치 (0,0)인데, 입력받을때 모든좌표에 100000을 더했으니..
    int x = 0 + MAX, y = 0 + MAX; 
    char c;
    scanf("%c", &c); //줄바꿈문자 제거
    for (int i = 0; i < m; i++) {
        scanf("%c", &c);

        switch (c) {
        case 'R':
            for (int i = 0; i < list_y[y].size(); i++) { //현재 y와 같은 y좌표들을 모두 검색
                int xx = list_y[y][i]; //탐색한 x좌표들
                if (x < xx) { //list는 sort되있으니, 현재 x좌표보다 큰 좌표를 만나면
                    x = xx; //현재 x좌표를 xx로 이동후 종료
                    break;
                }
            }
            break;
        case 'L':
            for (int i = list_y[y].size()-1; i >= 0; i--) { //감소하는방향으로
                int xx = list_y[y][i];
                if (x > xx) { //감소하는 방향이니 작은지 확인
                    x = xx;
                    break;
                }
            }
            break;
        case 'U':
            for (int i = 0; i < list_x[x].size(); i++) { 
                int yy = list_x[x][i]; 
                if (y < yy) { 
                    y = yy; 
                    break;
                }
            }
            break;
        case 'D':
            for (int i = list_x[x].size() - 1 ; i >= 0; i--) {
                int yy = list_x[x][i];
                if (y > yy) {
                    y = yy;
                    break;
                }
            }
            break;
        }
    }

    printf("%d %d\n", x - MAX, y - MAX);
}

int main(void) {
    init();
    func();


    return 0;
}