문제

BOJ 17143: 낚시왕 https://www.acmicpc.net/problem/17143

풀이

조건

• 낚시왕은 처음에 1번 열의 한 칸 왼쪽에 있다.
• 낚시왕은 가장 오른쪽 열의 오른쪽 칸에 이동하면 이동을 멈춘다.
• 다음은 1초 동안 일어나는 일이며, 아래 적힌 순서대로 일어난다.
  1. 낚시왕이 오른쪽으로 한 칸 이동한다.
  2. 낚시왕이 있는 열에 있는 상어 중에서 땅과 제일 가까운 상어를 잡는다. 상어를 잡으면 격자판에서 잡은 상어가 사라진다.
  3. 상어가 이동한다.
• 상어는 입력으로 주어진 속도로 이동하고, 속도의 단위는 칸/초이다. 상어가 이동하려고 하는 칸이 격자판의 경계를 넘는 경우에는 방향을 반대로 바꿔서 속력을 유지한채로 이동한다.
• 상어가 이동을 마친 후에 한 칸에 상어가 두 마리 이상 있을 수 있다. 이때는 크기가 가장 큰 상어가 나머지 상어를 모두 잡아먹는다.
• (r, c)는 상어의 위치, s는 속력, d는 이동 방향, z는 크기이다.
• d가 1인 경우는 위, 2인 경우는 아래, 3인 경우는 오른쪽, 4인 경우는 왼쪽을 의미한다.
• 두 상어가 같은 크기를 갖는 경우는 없고, 하나의 칸에 둘 이상의 상어가 있는 경우는 없다.

풀이 순서

• j(열)이 증가하는 것 자체가 낚시왕이 열을 한 칸씩 이동하는 것과 같은 2중 for문을 이용한다.
• 해당 열에서 가장 가까운 상어를 잡고 삭제한다.
• 상어를 이동시킨다.
  • 모든 상어를 속력만큼 이동시킨다.
  • 범위를 벗어나면 방향만 바꿔서 남은 속력만큼 이동시킨다.
• 겹치는 상어는 무게를 기준으로 하여 내림차순으로 정렬한 뒤 첫번째 상어(가장 무거운 상어)를 제외하고 나머지 상어를 pop() 하여 삭제한다.

코드

Python

import sys

r, c, m = map(int, sys.stdin.readline().rstrip().split())
# 북 - 남 - 동 - 서                                                                       
dx = [-1, 1, 0, 0]
dy = [0, 0, 1, -1]

# 낚시터 상태
graph = [[[] for _ in range(c)] for _ in range(r)]

for _ in range(m):
    x, y, s, d, z = map(int, input().split())
    graph[x - 1][y - 1].append([z, s, d - 1])


def move_shark():
    global graph
    # 이동한 뒤의 상어 상태를 저장할 배열
    board = [[[] for _ in range(c)] for _ in range(r)]

    for i in range(r):
        for j in range(c):
            if graph[i][j]:
                x, y = i, j
                z, s, d = graph[i][j][0]
                s_count = s
                while s_count > 0:
                    nx = x + dx[d]
                    ny = y + dy[d]
                    # 범위 벗어나면
                    if nx < 0 or nx >= r or ny < 0 or ny >= c:
                        # 방향 바꿔서 다시 이동
                        if d in [0, 2]:
                            d += 1
                        elif d in [1, 3]:
                            d -= 1
                        continue
                    # 범위 안 벗어나면
                    else:
                        # 이동
                        x, y = nx, ny
                        s_count -= 1
                # 이동 끝난 상태 저장
                board[x][y].append([z, s, d])

    # 이동 끝난 상태로 갱신
    for i in range(r):
        for j in range(c):
            graph[i][j] = board[i][j]


eat_count = 0

# j(열)이 증가하는 것 자체가 낚시왕이 열을 한 칸씩 이동하는 것과 같음
for j in range(c):
    for i in range(r):
        if len(graph[i][j]) > 0:
            value = graph[i][j][0]
            eat_count += value[0]
            graph[i][j].remove(value)
            break
    
    # 상어 이동
    move_shark()
    
    # 겹치는 상어 제거
    for p in range(r):
        for q in range(c):
            if len(graph[p][q]) > 1:
                # 상어 무게가 내림차순이 되게 정렬
                graph[p][q].sort(reverse=True)
                # 첫번째 상어(젤 무거운 상어) 제외한 나머지 상어 pop
                while len(graph[p][q]) >= 2:
                    graph[p][q].pop()

print(eat_count)

정리

• 각 상어마다 1칸씩 이동시키며 방향 전환을 하면 시간초과가 날 것 같아 수학적으로 해결하려 했는데 너무 어려워서 실패했다.
• 시간복잡도를 계산하는 연습을 더 해야겠다.