문제 링크

17142 - 낚시왕

문제 설명

낚시왕이 위와 같은 R*C 크기의 격자로 구성된 낚시장에서 상어 낚시를 한다. 각 칸에는 최대 상어 1마리가 있고, 각 상어는 크기와 속도, 바라보는 방향을 가진다.
낚시왕이 위의 그림 위치에서 시작해서 가장 오른쪽 열, 오른쪽 칸에 도달할때까지 1초간 이루어지는 일은 다음과 같다.

1. 낚시왕이 오른쪽으로 한칸 이동
2. 해당 열에서 가장 가까운 상어 잡기 -> 상어는 사라진다
3. 상어 이동
   : 이때 상어는 입력으로 주어진 속도로 이동하고, 격자의 경계를 넘으면 방향 반대 & 속도를 유지하고 이동한다.
4. 이동이 모두 끝나고 한칸에 2마리 이상이 있으면 가장 큰 상어가 나머지를 잡아먹는다.

다음과 같이 동작할때 낚시왕이 잡은 상어 크기의 합은?

문제 풀이

입력

board[r][c] : (r,c)칸에 있는 상어들의 번호와 크기를 저장하는 리스트
shark[i] : i번 상어의 [(r,c), 속력, 방향, 크기]를 저장하는 딕셔너리
라고 할때, 다음과 같이 입력받는다.

R,C,M = map(int, input().split())
board = [[[] for _ in range(C)] for _ in range(R)]
reverse = {1:2, 2:1, 3:4, 4:3}
shark = defaultdict()
for i in range(M):
    r, c, s, d, z = map(int, input().split())
    board[r-1][c-1].append((i, z)) # 상어번호와 크기 저장
    shark[i] = [(r-1,c-1),s,d,z]

매초간의 동작

1초간의 동작은 문제에서 주어진 순서 그대로 구현한다.

1. 낚시왕의 이동
   낚시왕의 현재 y좌표를 저장하는fisher를 1 증가시킨다.

    fisher += 1

2. 상어잡기
   낚시왕이 있는 열을 순차적으로 탐색하며 상어가 있으면 잡는다.

    for i in range(R):
        if len(board[i][fisher]) > 0:
            # 상어 있으면 잡기
            answer += board[i][fisher][0][1]
            del(shark[board[i][fisher][0][0]])
            board[i][fisher] = []
            break

3. 상어 이동하기
   move() 함수를 이용해서 상어를 잡는다.

	for s in shark.keys():
        move(s)

입력으로 주어진 속력만큼 이동시킨다. 격자를 벗어나면 방향을 바꾸고 남은 거리만큼 이동한다.

def move(sharknum):
    (x,y),s,d,z = shark[sharknum]
    board[x][y].remove((sharknum,z))

    for i in range(s):
        nx, ny = x+dx[d], y+dy[d]
        if in_bound(nx, ny):
            # 범위 안이면 한칸 이동
            x, y = nx, ny
        else:
            # 격자 벗어나면 방향 반대
            d = reverse[d]
            x, y = x+dx[d], y+dy[d]
    
    # 상어 위치 갱신
    shark[sharknum] = [(x,y),s,d,z]
    board[x][y].append((sharknum, z))

4. 이동 후 한칸에 2마리 이상?
   무거운 순으로 sorting해서 인덱스 0, 즉 제일 무거운 상어 제외하고 다 지운다.

    for i in range(R):
        for j in range(C):
            if len(board[i][j]) > 1:
                # 가장 무거운 순으로 sort
                sorted_board = sorted(board[i][j], key= lambda x:x[1], reverse=True)
                for s in sorted_board[1:]:
                    del(shark[s[0]])
                board[i][j] = [sorted_board[0]]

전체 코드

import sys
from collections import defaultdict

input = sys.stdin.readline
dx = [0, -1, 1, 0, 0]
dy = [0, 0, 0, 1, -1]

R,C,M = map(int, input().split())
board = [[[] for _ in range(C)] for _ in range(R)]
reverse = {1:2, 2:1, 3:4, 4:3}
shark = defaultdict()
for i in range(M):
    r, c, s, d, z = map(int, input().split())
    board[r-1][c-1].append((i, z)) # 상어번호와 크기 저장
    shark[i] = [(r-1,c-1),s,d,z]

def in_bound(x, y):
    if x in range(R) and y in range(C):
        return True
    return False

def move(sharknum):
    (x,y),s,d,z = shark[sharknum]
    board[x][y].remove((sharknum,z))

    for i in range(s):
        nx, ny = x+dx[d], y+dy[d]
        if in_bound(nx, ny):
            # 범위 안이면 한칸 이동
            x, y = nx, ny
        else:
            # 격자 벗어나면 방향 반대
            d = reverse[d]
            x, y = x+dx[d], y+dy[d]
    
    # 상어 위치 갱신
    shark[sharknum] = [(x,y),s,d,z]
    board[x][y].append((sharknum, z))


fisher = -1 # 낚시왕의 y좌표
answer = 0
for t in range(C): # 낚시왕이 오른쪽 끝까지 이동할때까지
    # 1. 낚시왕 이동하기
    fisher += 1

    # 2. 상어잡기
    for i in range(R):
        if len(board[i][fisher]) > 0:
            # 상어 있으면 잡기
            answer += board[i][fisher][0][1]
            del(shark[board[i][fisher][0][0]])
            board[i][fisher] = []
            break
    
    # 3. 상어 이동하기
    for s in shark.keys():
        move(s)
    
    # 4. 이동 후 한칸에 2마리 이상?
    for i in range(R):
        for j in range(C):
            if len(board[i][j]) > 1:
                # 가장 무거운 순으로 sort
                sorted_board = sorted(board[i][j], key= lambda x:x[1], reverse=True)
                for s in sorted_board[1:]:
                    del(shark[s[0]])
                board[i][j] = [sorted_board[0]]

print(answer)

소요시간

30분 >ㅇ<