17143 - 낚시왕

 

---

 

문제

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

17143번: 낚시왕

 

풀이

전형적인 시뮬레이션, 구현 문제

 

2차원 배열을 선언해주고 상어가 있는 위치에 [크기, 방향, 시간] 을 저장했다.

 

1차적으로 낚시왕의 열에서 행이 가장 작은 상어를 먹는다.

 

그리고 상어가 이동한다. 이 때 결과값을 저장할 빈 2차원 배열을 선언해둔다.

 

기존의 상어가 저장된 2차원 배열을 돌면서 상어가 존재하는 위치라면 저장해놓은 방향을 통해 한칸씩 이동한다.

만약 벽을 만나면 방향을 바꿔주고 한칸 이동시켜준다.

 

이동이 끝났다면, 빈 2차원 배열에 결과를 저장해준다. 만약 결과 위치에 상어가 존재한다면 크기가 큰 값만 저장해주면 된다. ( 빈 2차원 배열을 선언하지 않고 기존의 배열을 사용하게 된다면 아직 이동하지 않은 상어와 자리가 겹칠 수 있기에 따로 배열을 선언해준다.)

 

요렇게 계속 반복해주면 끝난다!

 

 

*

처음에는 상어의 위치와 크기를 max heap을 사용해서 저장했다. 

상어의 위치를 따로 저장 + 큰 크기부터 pop할 수 있으므로 위치가 겹치면 무시할 수 있기 때문이었는데,

이 문제는 배열의 크기만큼 상어가 들어올 수 있다. 따라서 시간복잡도면에서 크게 손해를 보기에 2차원 배열로 바꾸어서 풀이를 다시했다.  

 

 

 

코드

import sys
from sys import stdin
from collections import deque

import copy
import heapq

def getShark(loca):
    global sea, R, answer
    for i in range(R):
        if sea[i][loca][0] != 0:
            shark = sea[i][loca][0]
            answer += shark
            sea[i][loca] = [0, 0, 0]
            return

def changeDirection(d):
    if d == 0: return 1
    if d == 1: return 0
    if d == 2: return 3
    if d == 3: return 2

def moveShark():
    global sea, R, C

    t_sea = [[0] * C for _ in range(R)]
    for i in range(R):
        for j in range(C):
            t_sea[i][j] = [0, 0, 0]

    for i in range(R):
        for j in range(C):
            x, y = i, j
            z, d, s = sea[x][y]
            # 상어가 존재한다면
            if z != 0:
                for _ in range(s):
                    nx = x + dx[d]
                    ny = y + dy[d]

                    # 범위를 벗어난다면 방향을 변경해서 한 칸 가야한다.
                    if nx < 0 or nx >= R or ny < 0 or ny >= C:
                        d = changeDirection(d)
                        nx = x + dx[d]
                        ny = y + dy[d]

                    x = nx
                    y = ny

                if t_sea[x][y][0] != 0:
                    if t_sea[x][y][0] < z:
                        t_sea[x][y] = [z, d, s]
                else:
                    t_sea[x][y] = [z, d, s]
    return t_sea

# 위 아래 오른쪽 왼쪽
dx = [-1, 1, 0, 0]
dy = [0, 0, 1, -1]
answer = 0

R, C, M = map(int, stdin.readline().rstrip().split())
sea = [[0] * C for _ in range(R)]

for i in range(R):
    for j in range(C):
        sea[i][j] = [0, 0, 0]

for i in range(M):
    x,y,s,d,z = map(int, stdin.readline().rstrip().split())
    # 특정 위치에 크기, 방향, 속도 저장한다.
    sea[x-1][y-1] = [z, d-1, s]


for i in range(C):
    getShark(i)
    sea = moveShark()

print(answer)

 

후기

 

골1은 아닌거 같다. 상어가 벽을 만나면 이동하는 로직을 좀 다르게 짜는것도 있는거 같던데.. 단순 시뮬레이션으로도 풀리니 말이다. 골3, 4 정도..?