[Python] 31218번 자료 구조의 왕

https://www.acmicpc.net/problem/31218

31218번: 자료 구조의 왕

---

 

24/01/10

 

 

실수할 수도 있는 구현 문제로, 생각 없이 구현하다가는 시간 초과를 받을 수도 있는 문제이다.

 

약간의 세심함이 필요한 문제다.

---

 

문제 접근 방식:

 

 

초반 접근 방식은 문제에서 요구하는 것 처럼 쿼리 1, 쿼리 2, 쿼리 3에 대한 함수를 각각 구현하여, 각 요청을 받을 때마다 해당 함수를 불러오는 방식으로 구현했다.

 

나이브하게 구현했더니 시간초과가 났다. 문제는 쿼리 3에 있었다.

 

쿼리 3은 잔디 밭에 남아 있는 잔디의 개수를 출력하는 쿼리인데, 나는 그냥 잔디를 입력받아서 sum함수로 남아있는 잔디의 개수를 세주었다.

 

이는 매 쿼리 요청마다 잔디밭의 크기만큼의 시간 복잡도가 소요되는 비효율적인 구현이므로, 이 부분을 그냥 구현하면 안 됬었다.

 

나는 잔디를 깎을 때마다 전체 남아있는 잔디의 개수 또한 줄임으로써 쿼리 1에서 쿼리 3의 역할을 일정 부분 수행할 수 있도록 함수를 변경했다.

 

이렇게 하면 맞았습니다를 받을 수 있다.

 

쿼리가 $200,000$개이고, $n \times m$의 최댓값은 $1,000 \times 1,000 = 1,000,000$인데 쿼리 1을 잔뜩 넣어도 시간 초과가 나지 않는 이유는, 쿼리 1은 잔디가 하나도 없을 경우에는 바로 종료되기 때문이다.

 

따라서, 자칫하면 쿼리 1만 넣었을 경우에 소요되는 시간 복잡도가 $\mathcal{O}(QNM)$이라고 생각하기 쉽지만, 사실은 최악의 경우라도 $NM$을 넘지 않기 때문에 상관이 없다.

  

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더 보기를 누르면 확인할 수 있다.

# 31218번 자료 구조의 왕
# 구현, 시뮬레이션
import sys
input = sys.stdin.readline

def query_1(lawn, total, dy, dx, y, x, N, M):
    while True:
        if lawn[y-1][x-1] == 1:
            return lawn, total
        lawn[y-1][x-1] = 1
        total -= 1
        nxt_y, nxt_x = y+dy, x+dx
        if 0 < nxt_y <= N and 0 < nxt_x <= M:
            y, x = nxt_y, nxt_x
        else:
            return lawn, total

def query_2(lawn, y, x):
    print(lawn[y-1][x-1])
    return

def query_3(total):
    print(total)
    return

def main():
    N, M, Q = map(int, input().rstrip().split())
    lawn = [[0 for _ in range(M)] for _ in range(N)]
    total = N*M
    for _ in range(Q):
        q = input().rstrip()
        if q[0] == '1':
            q, dy, dx, y, x = map(int, q.split())
            lawn, total = query_1(lawn, total, dy, dx, y, x, N, M)
        elif q[0] == '2':
            q, y, x = map(int, q.split())
            query_2(lawn, y, x)
        else:
            query_3(total)
    return

main()