프로그래머스[Lv.3] - 공 이동 시뮬레이션

문제 설명

n행 m열의 격자가 있습니다. 격자의 각 행은 0, 1, ..., n-1번의 번호, 그리고 각 열은 0, 1, ..., m-1번의 번호가 순서대로 매겨져 있습니다. 당신은 이 격자에 공을 하나 두고, 그 공에 다음과 같은 쿼리들을 날리고자 합니다.

• 열 번호가 감소하는 방향으로 dx칸 이동하는 쿼리 (query(0, dx))
• 열 번호가 증가하는 방향으로 dx칸 이동하는 쿼리 (query(1, dx))
• 행 번호가 감소하는 방향으로 dx칸 이동하는 쿼리 (query(2, dx))
• 행 번호가 증가하는 방향으로 dx칸 이동하는 쿼리 (query(3, dx))

단, 공은 격자 바깥으로 이동할 수 없으며, 목적지가 격자 바깥인 경우 공은 이동하다가 더 이상 이동할 수 없을 때 멈추게 됩니다. 예를 들어, 5행 × 4열 크기의 격자 내의 공이 3행 2열에 있을 때 query(3, 10) 쿼리를 받은 경우 공은 4행 2열에서 멈추게 됩니다. (격자의 크기가 5행 × 4열이므로, 0~4번 행과 0~3번 열로 격자가 구성되기 때문입니다.)

격자의 행의 개수 n, 열의 개수 m, 정수 x와 y, 그리고 쿼리들의 목록을 나타내는 2차원 정수 배열 queries가 매개변수로 주어집니다. n × m개의 가능한 시작점에 대해서 해당 시작점에 공을 두고 queries 내의 쿼리들을 순서대로 시뮬레이션했을 때, x행 y열에 도착하는 시작점의 개수를 return 하도록 solution 함수를 완성해주세요.

https://school.programmers.co.kr/learn/courses/30/lessons/87391

프로그래머스

---

 

 

 

 

 

 

제한 사항

• 1 ≤ n ≤ 109
• 1 ≤ m ≤ 109
• 0 ≤ x < n
• 0 ≤ y < m
• 1 ≤ queries의 행의 개수 ≤ 200,000
  • queries의 각 행은 [command,dx] 두 정수로 이루어져 있습니다.
  • 0 ≤ command ≤ 3
  • 1 ≤ dx ≤ 109
  • 이는 query(command, dx)를 의미합니다.

---

 

 

 

 

 

 

풀이

너무 어려웠다...

시뮬레이션하는 것은 쉽지만 모든 칸에 대해 시뮬레이션을 돌리면 시간초과가 발생한다.

따라서 다른 접근법이 필요하다.

 

기본적인 접근법은 거꾸로 진행하는 것이다.

결국 목표지점에서 종료되어야 하므로 종료지점에서 출발하여 거꾸로 진행하면 시작하는 위치를 알 수 있다.

이때, 시작하는 위치는 범위로 나타난다.

왜냐하면 임시 목표지점이 배열의 끝부분에 있다면 이동이 무시되기 때문에 가능한 부분이 늘어나는 것이다.

단, 가능한 부분이 늘어나려면 무조건 배열의 끝부분에 있으면서 해당 방향으로 이동해야 한다.

예를 들어, 가능한 영역의 y값이 0일때, 위로 이동하려 한다면 가능한 영역을 아래로 하나 늘려야 한다.

만약 그렇지 않은 상태라면 반대방향으로 가능영역을 이동시켜야 한다.

이때, 예외처리를 해야 한다.

예를 들어, 오른쪽으로 이동할 때 가능영역의 왼쪽이 배열의 오른쪽을 넘어갔다면 가능한 영역이 없다고 판단해야 한다.

---

 

 

 

 

 

전체 코드

#include <string>
#include <vector>
#include <iostream>

using namespace std;

vector<int> dy = {0, 0, -1, 1};
vector<int> dx = {-1, 1, 0, 0};

long long solution(int n, int m, int x, int y, vector<vector<int>> queries) {
    long long answer = 0;
    
    long long X = y;
    long long Y = x;
    
    long long up = Y;
    long long down = Y;
    long long left = X;
    long long right = X;
    
    for(int i = queries.size()-1; i >= 0; i--)
    {
        auto query = queries[i];
        
        //l, r, u, d
        if((query[0]==0 && left==0) || (query[0]==1 && right==m-1) || (query[0]==2 && up==0) || (query[0]==3 && down==n-1))
        {
            //plus
            switch(query[0])
            {
                case 0:
                    right = right + query[1] >= m ? m-1 : right + query[1];
                    break;
                case 1:
                    left = left - query[1] < 0 ? 0 : left - query[1];
                    break;
                case 2:
                    down = down + query[1] >= n ? n-1 : down + query[1];
                    break;
                case 3:
                    up = up - query[1] < 0 ? 0 : up -query[1];
                    break;
            }
        }
        else
        {
            //move
            switch(query[0])
            {
                case 0:
                    right = right+query[1] >= m ? m-1 : right+query[1];
                    left = left+query[1];
                    if(left >= m) return 0;
                    break;
                case 1:
                    right = right-query[1];
                    left = left-query[1] < 0 ? 0 : left-query[1];
                    if(right < 0) return 0;
                    break;
                case 2:
                    up = up+query[1];
                    down = down+query[1] >= n ? n-1 : down+query[1];
                    if(up >= n) return 0;
                    break;
                case 3:
                    up = up-query[1] < 0 ? 0 : up-query[1];
                    down = down-query[1];
                    if(down < 0) return 0;
                    break;
            }
        }
    }

    answer = (down - up + 1) * (right - left + 1);
    
    return answer;
}

---