프로그래머스 공 이동 시뮬레이션 Kotlin (그리디)

문제 출처 : https://programmers.co.kr/learn/courses/30/lessons/87391 

코딩테스트 연습 - 공 이동 시뮬레이션

공 이동 시뮬레이션

문제 설명

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 ≤ 10^9
  • 이는 query(command, dx)를 의미합니다.

입출력 예 설명

입출력 예 #1

• 다음 애니메이션은 4개의 가능한 시작점에 대한 모든 시뮬레이션을 나타낸 것입니다.

• 어떤 곳에서 출발하더라도 항상 0행 0열에 도착하기 때문에, 4를 return 해야 합니다.

입출력 예 #2

• 다음 애니메이션은 10개의 가능한 시작점에 대한 모든 시뮬레이션을 나타낸 것입니다.

• 0행 1열, 1행 1열에서 출발했을 때만 0행 1열에 도착하므로, 2를 return 해야 합니다.

풀이

월간 코드 챌린지 시즌 3에 나왔던 문제이다.

당시에는 못 풀었는데, 이번에도 못 풀어서 해설 보고 풀었다.

x,y에서 역으로 탐색해서 가능한 시작 좌표들을 구하는 것은 알겠는데, 이를 어떻게 구할지에 대한 답을 찾지 못했다.

 

해결해야 할 과제는 n,m이 10억이고 쿼리가 20만, 쿼리에서 이동 명령의 최대 칸 수는 10억으로, 이를 직접 시뮬레이션 돌리면 시간 초과다. 따라서 우리는 시뮬레이션을 돌려보지 않고도 정답을 알아내야 한다.

주어지는 쿼리 연산의 값을 모아서 일괄 처리하는 방법, 쿼리 연산을 매번 수행하되, 효율적으로 하는 방법이 있는데,

이 문제에선 중간에 그래프 범위를 나가는 경우 값을 모아서 일괄처리 하긴 힘들다.

따라서 매번 쿼리를 수행하되 효율적으로 처리해야 하는데, 핵심은 다음과 같다.

(r1,c1) 정답(시작점)이 될 수 있는 범위의 시작 부분

(r2,c2) 정답(시작점)이 될 수 있는 범위의 끝 부분

즉 2차원 그래프의 r1~r2, c1~c2 범위 내에 있는 개수가 정답이 되고, 이는 (r2-r1+1) * (c2-c1+1)로 구할 수 있다.

                0 -> {//우
                    c2+=cnt
                    if(c2>=m) c2 = m-1
                    if(c1!=0) c1+=cnt
                    if(c1>=m) return 0
                }

오른쪽으로 이동하는 경우다.

x,y(도착점)기준으로 시작점을 찾아야 하기 때문에 주어진 쿼리를 역순으로 탐색해야 하고, 방향 또한 반전해야 한다.

따라서 위 코드에서 사실 입력 방향은 왼쪽이지만 역전시켜주어 오른쪽 이동하는 것이다.

오른쪽으로 이동하는 경우에, c1,c2에서 c1이 0인 경우(벽에 붙어있는 경우)는 c1을 이동하지 않는다. 원래대로라면 왼쪽으로 움직여야 하지만 더 이상 갈 수 없음을 의미한다. c1이 0이 아닌 경우는 cnt(dx)만큼 이동하고, 이때  c1이 오른쪽 벽을 넘어가는 경우는 원래 정방향으로 이동할 때 이 시작점에서 출발한 루트가 절대 x,y에 도착할 수 없음을 의미하기 때문에 바로 0을 리턴한다.

그리고 c2는 cnt(dx)만큼 이동하는데 c2가 우측 벽을 넘어간다면 우측 벽에 딱 붙여준다.

 

나머지 3 방향에 대해서도 위와 같은 논리를 적용해서 식을 구현하면 된다.

 

코드

/*
쿼리 20만
n,m 10억
실제 시뮬레이션 없이 이동한 값을 상태로 나타내기
x,y에서 갈 수 있는 r1,c1  r2,c2  가능한 값의 범위
x,y에서 시작해 쿼리 역순 실행
*/
class Solution {
    val oper = LongArray(2)
    fun solution(n: Int, m: Int, x: Int, y: Int, queries: Array<IntArray>): Long {
        var r1 = x
        var r2 = x
        var c1 = y
        var c2 = y
        //연산 결과 추출
        for(i in queries.size-1 downTo 0){
            val d = queries[i][0]
            val cnt = queries[i][1]
            //방향 반전
            when(d){
                0 -> {//우
                    c2+=cnt
                    if(c2>=m) c2 = m-1
                    if(c1!=0) c1+=cnt
                    if(c1>=m) return 0
                }
                1 -> {//좌
                    c1-=cnt
                    if(c1<0) c1 = 0
                    if(c2!=m-1) c2-=cnt
                    if(c2<0) return 0
                }
                2 -> {//하
                    r2+=cnt
                    if(r2>=n) r2 = n-1
                    if(r1!=0) r1+=cnt
                    if(r1>=n) return 0
                }
                else -> {//상
                    r1-=cnt
                    if(r1<0) r1 = 0
                    if(r2!=n-1) r2-=cnt
                    if(r2<0) return 0
                }
            }
        }
        return (r2-r1+1).toLong() * (c2-c1+1).toLong()
    }
}