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

※사용언어 : 파이썬 ※

 

▼ 문제 링크 ▼

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

프로그래머스

 

---

 

문제 설명

◇ 문제를 간단히 요약하자면 다음과 같습니다.

▶ 주어진 쿼리 문에 맞춰 공을 움직여, 주어진 x, y 에 공이 도착할 수 있는 시작 위치를 찾는 문제입니다.

 

◇ n행 m열의 격자의 최대 크기가 10의 9승입니다. 그러므로 모든 격자의 칸에서 쿼리를 돌려 x, y에 도착하는지 확인하는 완전 탐색으로 풀기에는 시간이 부족합니다. 그러므로 도착점을 기준으로 쿼리를 반대로 돌려 도착점에 도달할 수 있는 시작 좌표들을 한정 짓는 방식을 사용해야합니다.

 

◇ 입출력 예 #1 과 함께 풀이방법을 서술하겠습니다.

▶ 2X2 의 격자가 주어지고 도착 좌표는 (0,0) 입니다.

▶ 쿼리문의 뱡향은 "↑ ← → ← ↑" 이며, 모든 쿼리문이 1칸씩 움직입니다.

▶  풀이과정

1. (0,0)에서 시작합니다.

2. 거꾸로 쿼리를 탐식핼 것이기 때문에 이동방향을 반대로 바꿔줍니다.

3. 이동 방향을 반대로 바꾼 쿼리를 거꾸로 탐색할 것이기 때문에, 거꾸로 뒤집어줍니다. 

도착지점인 (0,0)을 색칠하고, 쿼리를 돌리면서 갈 수 있는 좌표들을 선홍색으로 색칠해가겠습니다.

4. 아래로 움직입니다.

아래로 움직이는 경우는 크게 2가지가 있습니다. (0,0) 좌표에서 아래로 움직인 경우

(1,0) 좌표에서 아래로 움직인 경우 (벽에 부딪히겠지만 움직일 순 있습니다.)

그런데, 우리는 (0,0)에서 시작했는데 (1,0) 좌표에서 아래로 내려갈 수 있나요? 라고 의문을 가질 수 있습니다. 

지금까지 온 길을 거꾸로 생각해볼까요? 우리가 온 길을 거꾸로 돌리게 되면, 위로 한칸 올라가는게 됩니다. (0,1)좌표에서 한칸 위로 올라가면, 도착지인 (0,0)을 만나게 됩니다. 즉 우리는 사실상 위로 한칸 더 올라가기 위해 갈 수 있는 영역을 늘려주고 있었던 것 입니다. 이 원리는 상하좌우 어디로든 움직일때마다 똑같이 적용됩니다.

5. 오른쪽으로 움직입니다.

이때 (0,0)에서도 오른쪽으로 움직일 수 있고, (1, 0)에서도 움직일 수 있기 때문에 다음과 같이 표를 색칠할 수 있습니다.

6. 왼쪽으로 움직입니다.

오른쪽에서 왼쪽으로 움직이면서, 오른쪽 영역(0,1 과 0,2)이 더는 필요없게 되었습니다. 그러므로 색칠을 하지 않습니다.

7. 왼쪽으로 움직입니다.

다시 오른쪽으로 가면서, 오른쪽 영역이 칠해집니다.

8. 아래로 움직입니다.

현재 위치가 (0,1) 이든 (0,2)이든 아래로 움직이게 되면 색칠된 영역에서 움직이게 됩니다.

(0,1) → (0,2)

(0,2) → 벽에 부딪힘

그러므로 색칠 영역이 유지되고 쿼리가 끝나게 됩니다.

 

---

 

문제풀이(With Python)

def solution(n, m, x, y, queries):
    answer = 0
    x_min, x_max, y_min, y_max = x, x, y, y

    for i in range(len(queries)-1, -1, -1):
        way, dist = queries[i]

        if way == 0: # 실제: 좌측 이동 / 거꾸로: 우측 이동
            y_max += dist
            if y_max > m-1: # 벽에 부딪힌 경우
                y_max = m-1
            if y_min != 0: 
                y_min += dist # 벽이 아닌 경우, 갈 수 있는 지역 축소

        elif way == 1: # 실제: 우측 이동 / 거꾸로: 좌측 이동
            y_min -= dist
            if y_min < 0: # 벽에 부딪힌 경우
                y_min = 0 
            if y_max != m-1:
                y_max -= dist # 벽이 아닌 경우, 갈 수 있는 지역 축소

        elif way == 2: #실제: 위로 이동 / 거꾸로: 아래로 이동
            x_max += dist
            if x_max > n-1: # 벽에 부딪힌 경우
                x_max = n-1
            if x_min != 0: 
                x_min += dist # 벽이 아닌 경우, 갈 수 있는 지역 축소

        else: #실제: 아래 이동 / 거꾸로: 위에 이동
            x_min -= dist
            if x_min < 0:  # 벽에 부딪힌 경우
                x_min = 0
            if x_max != n-1: 
                x_max -= dist # 벽이 아닌 경우, 갈 수 있는 지역 축소
                
        if y_min > m-1 or y_max < 0 or x_min > n-1 or x_max < 0 :
            return answer
    else:
        answer = (y_max - y_min + 1) * (x_max - x_min +1)

    return answer