문제

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

---

입력

• 격자의 행의 개수 n
• 열의 개수 m
• 정수 x와 y
• 쿼리들의 목록을 나타내는 2차원 정수 배열 queries

---

출력

x행 y열에 도착하는 시작점의 개수

---

풀이

제한조건

• 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)를 의미합니다.

접근방법

방법1 DP
처음 생각한것은 DP로 접근하기 였다.
각 좌표에서 탐색을 하며, 도착점에 도착한다면, 중간 경로들을 기록하며
N 번의 이동이 남았을 때, 특정위치위에 있다면 도착이 보장되는것을 활용하려했다.
하지만 경우의 수가 너무 많고 코드가 복잡해져서 다른 방법을 찾기로했다.

방법2. 시뮬레이션
도착지점에서부터 역으로 시뮬레이션을 하며 예상 범위를 찾는방식이다.
별다른 해결방법이 있는것이 아니라, 도착지에서부터 query로 주어진 움직임을 역방향으로 수행하며, 범위를 찾아나간다.

그럼 상하좌우 4방향의 경계가 구해지는데
경계의 내부에 있는 좌표가 모두 도착지점으로 갈 수 있는 지점들이다.

각 범위가 최외각라인에 도착했을때의 처리만 신경써서 해주자.

---

코드

class Solution {
    public long solution(int n, int m, int x, int y, int[][] queries) {
        long left = y;
        long right = y;
        long top = x;
        long bottom = x;

        for (int i = queries.length - 1; i >= 0; i--) {
            int direction = queries[i][0];
            int dist = queries[i][1];

            if (direction == 0) { // LEFT
                if (left != 0) 
                    left += dist;
                right = Math.min(m - 1, right + dist);
            } else if (direction == 1) { // RIGHT
                if (right != m - 1) 
                    right -= dist;
                left = Math.max(0, left - dist);
            } else if (direction == 2) { // UP
                if (top != 0) 
                    top += dist;
                bottom = Math.min(n - 1, bottom + dist);
            } else if (direction == 3) { // DOWN
                if (bottom != n - 1) 
                    bottom -= dist;
                top = Math.max(0, top - dist);
            }

            // 범위가 격자를 벗어나면 더 이상 유효한 시작점이 없음
            if (left >= m || right < 0 || top >= n || bottom < 0) {
                return 0;
            }
        }

        // 최종적으로 가능한 시작점의 범위가 격자 내에 있다면 개수를 반환
        return (right - left + 1) * (bottom - top + 1);
    }
}