[Algorithm] 공 이동 시뮬레이션

📋 문제

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 함수를 완성해주세요.

제한사항

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

입출력 예

2	2	0	0	[[2,1],[0,1],[1,1],[0,1],[2,1]]	4
2	5	0	1	[[3,1],[2,2],[1,1],[2,3],[0,1],[2,1]]	2

 

✏️ 풀이

모든 경우를 진행한다면 무조건 시간초과가 날 것이라고 생각했다. 그래서 반대로 쿼리를 진행하면서 확인하는 방법을 사용했다.

 

만약 ←(1번째) ↓(2번째) ↓(3번째) →(4번째)으로 쿼리를 날린다면 위치해야 하는 지점에서 시작해서 반대로 →(4번째) ↓(3번째) ↓(2번째) ←(1번째)로 역순으로 진행한다. 또한 방향도 반대가 되어 최종적으로 ←(4번째) ↑(3번째) ↑(2번째) →(1번째)를 실행해보는 것이다.

 

가장 중요하다고 생각하는 점은 벽에 공이 위치해 있다면 범위로 계산이 된다는 것이었다.

만약 공이 위 이미지의 해당 위치로 이동해야 하고 현재 수행하는 쿼리가 오른쪽으로 두칸 가는 상황이라면 다음과 같은 상황에 해당 위치로 이동할 수 있다.

두 위치 모두 왼쪽으로 두칸 이동했을 때 같은 결과를 나타내기 때문이다. 따라서 역으로 쿼리를 수행하면서 주의해야한다. 이 문제를 해결하기 위해서 minX, maxX, minY, maxY라는 4개의 변수를 선언했다. 각각 범위의 상단, 하단, 좌측, 우측을 가르킨다. 다음 이미지를 보면 이해하기 더 쉽다.

범위가 될때는 조건이 있는데 기존 쿼리의 방향과 해당 방향의 벽이 바로 옆에 있어야 한다는 것이다. 이 조건일때 좌표를 (상단 하단), (좌측 우측) 둘다 수정하는 것이 아닌 하나만 수정하여 범위로 구성되도록 한다. 

 

한가지 더 주의할 점이 있는데 만약 반대로 이동했을 때 사각형 범위를 아에 벗어나는 상황이다. 현재 범위가 다음과 같이 구성되어 있을때를 생각해보자

이때 만약 좌측으로 3회 가는 경우에는 어떻게 될까?

파란색 테두리가 아에 격자 밖으로 넘어간다. 만약 일부만 넘어간 경우 표 내부에 있는 부분은 가능하므로 계속 진행할 수 있지만 아에 나가는 경우에는 가능한 경우가 없다는 의미로 0을 바로 반환했다. 각 최대값이 0 미만이 되거나, 최소값이 격자의 크기(n, m)이상이 될 때로 판단했다.

 

모든 쿼리를 반대로 순회하고 구한 minX, maxX, minY, maxY는 변의 위치를 의미하므로 넓이를 구해준다.

(maxX - minX + 1) * (maxY - minY + 1)

 

또 한가지 내 발목을 잡은 문제가 있었는데 그건 바로 BigInt였다. n과 m의 범위가 10^9로 계산할 때 표현 범위를 벗어날 수 있기 때문에 BigInt 처리를 해주고 문제를 해결했다.

 

⌨️ 코드

function solution(n, m, x, y, queries) {
  var answer = -1;

  let minX = BigInt(x),
    maxX = BigInt(x),
    minY = BigInt(y),
    maxY = BigInt(y);

  queries.reverse();
  for (const query of queries) {
    let [dist, cnt] = query;
    cnt = BigInt(cnt);

    if (dist === 0) {
      if (minY !== 0n) minY = minY + cnt;
      maxY = maxY + cnt;
    } else if (dist === 1) {
      if (maxY !== BigInt(m - 1)) maxY = maxY - cnt;
      minY = minY - cnt;
    } else if (dist === 2) {
      if (minX !== 0n) minX = minX + cnt;
      maxX = maxX + cnt;
    } else if (dist === 3) {
      if (maxX !== BigInt(n - 1)) maxX = maxX - cnt;
      minX = minX - cnt;
    }

    if (maxX < 0 || maxY < 0 || minX >= n || minY >= m) return 0;
    minX = minX < 0n ? 0n : minX;
    maxX = maxX >= BigInt(n) ? BigInt(n - 1) : maxX;
    minY = minY < 0n ? 0n : minY;
    maxY = maxY >= BigInt(m) ? BigInt(m - 1) : maxY;
  }

  answer = (maxX - minX + 1n) * (maxY - minY + 1n);

  return answer;
}