[프로그래머스] 공 이동 시뮬레이션

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

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

 

처음에는 BFS로 접근하려고 했으나 범위를 보고 다르게 생각하였다. 이분 탐색인가 했으나 방법이 떠오르지 않았고 답이 사각형 모양으로 나와 범위를 기억하는 것으로 접근하였다.

 

범위를 top, left, right, bottom 으로 변수를 받아 기억하였고 구하면 해당 좌표를 가진 사각형의 넓이를 구하면 된다.

공이 도착하는 지점에서 queries 를 거꾸로 돌려 가능한 시작점의 범위를 구하면 된다.

예를 들어, top = 0 이고 0 이 되기 전 행이 감소하는 방향으로 dx 칸 이동하는 명령을 받았다면 0 + 1, 0 + 2, ..., 0 + dx의 위치에서 가능하므로 top = 0, bottom = bottom + dx 로 범위가 설정된다. top = 0 이 아니라면 top = top + dx, bottom = bottom + dx 이다. (top 위로 갈 수 있는 목적지가 있기 때문이다.)

 

단, 격자의 범위를 벗어나면 안 되므로 [0, n] ~ [0, m] 제한을 둔다. 그리고 t 가 n - 1 을 넘어가는 경우(l > m - 1, r < 0, b < 0) 목적지에 도달할 수 없는 경우이므로 answer = 0 으로 처리해야 한다. (테스트 33, 34)

 

def solution(n, m, x, y, queries):
    answer = 0
    t, l, r, b = x, y, y, x
    queries.reverse()
    
    for i, j in queries:
        if i == 0:
            temp = (r + j) if r + j < m else m - 1
            
            if l == 0: 
                r = temp
            else: 
                l, r = l + j, temp
        if i == 1:
            temp = (l - j) if l - j >= 0 else 0
            
            if r == m - 1: 
                l = temp
            else: 
                l, r = temp, r - j
        if i == 2:
            temp = (b + j) if b + j < n else n - 1
            
            if t == 0:
                b = temp
            else:
                t, b = t + j, temp
        if i == 3:
            temp = (t - j) if t - j >= 0 else 0
            
            if b == n - 1:
                t = temp
            else:
                t, b = temp, b - j
    
        if l > m - 1 or r < 0 or t > n - 1 or b < 0:
            break
    
    else:
        answer = ((b - t) + 1) * ((r - l) + 1) 
        
    return answer