백준 17143번 낚시왕

 

문제

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

소감

시뮬레이션 알고리즘으로 분류되는 문제들의 특징을 검색해본 적 있다. 머리를 많이 굴릴 필요는 없지만 코드가 매우 길다는 점이다. 그런데 이 문제는 머리를 좀 써야 했다. 특정 부분에서 시간 복잡도를 줄여야 했는데, 그 부분에 직접 구상한 수학 공식을 적용해야 했기 때문이다. 아래에서 코드를 통해 설명을 이어나가겠다.

코드

import sys
input = sys.stdin.readline

def fish(sec):
    for i in range(1, R+1):
        if graph[i][sec]:
            size = shark_info[graph[i][sec]][1]
            graph[i][sec] = 0 # 상어 없앰
            return size # 크기
    return 0

def move():
    global graph, dir
    new_graph = [[0 for _ in range(C+1)] for _ in range(R+1)]
    new_dir = [0 for _ in range(M+1)]
    for r in range(1, R+1):
        for c in range(1, C+1):
            if graph[r][c]:
                s = shark_info[graph[r][c]][0] # 속력
                d = dir[graph[r][c]] # 시작 방향
                nr, nc = r, c
                L = 0 # R or C
                l = 0 # r or c (시작 방향)
                if d <= 2:
                    L = R
                    l = r
                else:
                    L = C
                    l = c
                diff = 0
                if d == 1 or d == 4: diff = 2 * L - l - 1
                else: diff = l - 1
                
                x = s % (2*L-2) + diff
                x %= (2*L-2)
                if d <= 2:
                    if x <= R-1:
                        nd = 2
                        nr = x+1
                    else:
                        nd = 1
                        nr = 2*R-x-1
                else:
                    if x <= C-1:
                        nd = 3
                        nc = x+1
                    else:
                        nd = 4
                        nc = 2*C-x-1
                if not (new_graph[nr][nc] and shark_info[new_graph[nr][nc]][1] > shark_info[graph[r][c]][1]): #'이미 점령한 상어가 더 큰 경우'가 아니면
                    new_dir[graph[r][c]] = nd # 방향 업데이트
                    new_graph[nr][nc] = graph[r][c] # 위치 업데이트
                    
    graph = [row[:] for row in new_graph]
    dir = new_dir[:]

R, C, M = map(int, input().split())
graph = [[0 for _ in range(C+1)] for _ in range(R+1)]
shark_info = [0] # 속력, 크기
dir = [0] # 방향
for i in range(1, M+1):
    r, c, s, d, z = map(int, input().split())
    graph[r][c] = i
    shark_info.append([s,z])
    dir.append(d)

res = 0
for i in range(1, C+1): # C초 동안 매 초마다 / O(100)
    # 1. 낚시왕이 상어 포획
    res += fish(i) # O(100) => O(100x100) = O(10,000)
    # 2. 상어 이동
    move()
    
print(res)

코드 설명

일단 이 문제의 시간제한은 1초이다. 1초는 약 1억번의 연산이라 생각한다면, 코드의 시간복잡도가 O(100,000,000)를 넘으면 안된다. 코드의 큰 뼈대를 보면 다음과 같다. 

코드의 큰 뻐대

fish()는 낚시꾼이 상어 포획 함수이며 땅이랑 가장 가까이 위치한 상어를 포획한다.move()는 상어들이 1초동안 이동하는 함수이다.

 

문제에서 준 입력값의 범위는 다음과 같다.

입력값의 범위

 

그러면 for 문은 최대 100번 돌게 된다. 그리고 fish() 함수는 구현이 쉬우므로, 먼저 살펴보자.

가장 땅이랑 가까운 상어를 포획

 

이 함수는 딱 봐도 시간복잡도가 O(100)이다. 그러면 move()함수가 당연히 더 오래 걸릴 것이란 걸 눈치 챌 수 있다.

이 move() 함수에게 허용되는 시간복잡도는 최대 O(1000,000)가 된다.

자, 여기서 한가지 고백을 하자면, 처음에 이 부분을 구현할 때 모든 상어를 순회하면서 속력을 하나씩 쪼개어서, 그러니깐 속력(1초에 이동하는 칸 수)가 9이면 9번을 나눠서 1초 뒤에 도달하는 지점을 찾아주었다. 그렇게 되면 최소 O(MxS)의 시간복잡도가 나오게 된다. M은 최대 10,000(RxC)이고, S는 최대 1000이므로 최종적으로 move() 함수 시간복잡도는 O(10,000,000)가 된다. 그러면 함수 바깥에 for문이 O(100)이었으니깐, 전체 코드의 시간복잡도는 1초를 넘게 된다. 그리고 여기서 또 놓친 조건이 있는데, 그건 바로 상어가 이동을 한 지점에 또 다른 상어가 있을 경우 더 큰 상어가 작은 상어를 잡아먹는다는 것이다. (문제를 꼼꼼히 읽자)

 

그렇다면 나에게 많은 시련을 준 move()함수는 어떻게 생겼냐 하면...

new_graph, new_dir는 새로운 상어 위치와 방향을 저장할 변수이며, 코드 맨 뒤에서 보듯이 graph, dir를 대체하게 된다.

move() 함수의 핵심은 수직, 수평으로 움직이는 상어들이 loop를 갖는다는 것이다. 말로 설명하기 보다는 그림을 그려가며 하는 것이 직관적이니까 그림을 그려보았다. 그림에 나오는 부분은 일부분이니, 나머지 부분은 직접 계산해보길 권장한다.

그림을 그려야 확실히 이해가 잘 되는 것 같다.