[백준 17143] 낚시왕

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

17143번: 낚시왕

---

접근

이번 문제에는 상어들의 step 크기가 최대 1000이다. 따라서 최대 RxC 마리의 상어들의 모두 1000의 크기만큼 이동할 때 한 칸씩 이동하도록 구현하면 시간초과가 발생한다. 따라서 상어들의 step 크기를 줄여야했다.

 

이를 위해 규칙을 찾아보면 상하로 움직이는 상어들은 (R-1) x 2배, 좌우로 움직이는 상어들은 (C - 1) x 2배일 때 같은 자리로 돌아오게 된다. 따라서 위의 연산으로 나눈 나머지로 step을 설정한다면 이동 횟수를 줄일 수 있다.

 

구현

- 상어들의 정보를 입력받는다.

- 방향이 상하라면 s를 (R - 1) x 2로 나눈 나머지로 변환하고 좌우라면 (C - 1) x 2로 나눈 나머지로 변환한다.

- 이후 r, c 위치에 s, d, z를 저장한다.

R, C, M = map(int, input().split())
board = [[[] for _ in range(C)] for _ in range(R)]

dy = [-1, 1, 0, 0]
dx = [0, 0, 1, -1]
for _ in range(M):
    r, c, s, d, z = map(int, input().split())
    r -= 1
    c -= 1
    d -= 1
    if d == 0 or d == 1:
        s %= ((R - 1) * 2)
    else:
        s %= ((C - 1) * 2)
    board[r][c] = [s, d, z]

- 낚시왕이 오른쪽으로 움직이기 때문에 C만큼 for문으로 탐색한다.

- 이제 각각의 위치를 find_shark 함수로 전달하여 가장 가까운 상어를 찾아 answer에 저장한다.

- 이후 move_shark에 상어들의 정보가 저장된 2차원 리스트인 board를 전달하여 상어를 이동시킨 새로운 board를 전달받는다.

for i in range(C):
    answer += find_shark(i)
    board = move_shark(board)

- 상어들이 이동한 결과를 담을 새로운 2차원 리스트인 new_board를 생성한다.

- 기존의 board를 탐색하여 상어가 존재하는 곳일 때 상어를 이동시킨다.

- s만큼 이동시키다가 맵을 벗어났을 때 방향을 변환하여 이동한다.

- 상어가 새로운 위치에 도착했을 때 이미 상어가 있다면 크기를 비교하여 변경하고 아니라면 해당 위치에 상어의 정보를 저장한다.

- 최종적으로 new_board를 반환한다.

def move_shark(board):
    new_board = [[[] for _ in range(C)] for _ in range(R)]

    for y in range(R):
        for x in range(C):
            if board[y][x] and board[y][x][0] != -1:
                s, d, z = board[y][x][0], board[y][x][1], board[y][x][2]
                ny, nx = y, x
                step = s
                while step:
                    ny += dy[d]
                    nx += dx[d]
                    if not check_range(ny, nx):
                        ny -= dy[d]
                        nx -= dx[d]
                        d = change_direction(d)
                        ny += dy[d]
                        nx += dx[d]

                    step -= 1

                if new_board[ny][nx]:
                    if new_board[ny][nx][2] < z:
                        new_board[ny][nx] = [s, d, z]
                else:
                    new_board[ny][nx] = [s, d, z]
    return new_board

---

전체 코드

import sys
input = sys.stdin.readline

def check_range(y, x):
    return (0 <= y < R) and (0 <= x < C)

def find_shark(col):
    for y in range(R):
        if board[y][col]:
            board[y][col][0] = -1
            return board[y][col][2]
    return 0

def change_direction(d):
    if d == 0:
        return 1
    elif d == 1:
        return 0
    elif d == 2:
        return 3
    else:
        return 2

def move_shark(board):
    new_board = [[[] for _ in range(C)] for _ in range(R)]

    for y in range(R):
        for x in range(C):
            if board[y][x] and board[y][x][0] != -1:
                s, d, z = board[y][x][0], board[y][x][1], board[y][x][2]
                ny, nx = y, x
                step = s
                while step:
                    ny += dy[d]
                    nx += dx[d]
                    if not check_range(ny, nx):
                        ny -= dy[d]
                        nx -= dx[d]
                        d = change_direction(d)
                        ny += dy[d]
                        nx += dx[d]

                    step -= 1

                if new_board[ny][nx]:
                    if new_board[ny][nx][2] < z:
                        new_board[ny][nx] = [s, d, z]
                else:
                    new_board[ny][nx] = [s, d, z]
    return new_board


R, C, M = map(int, input().split())
board = [[[] for _ in range(C)] for _ in range(R)]

dy = [-1, 1, 0, 0]
dx = [0, 0, 1, -1]
for _ in range(M):
    r, c, s, d, z = map(int, input().split())
    r -= 1
    c -= 1
    d -= 1
    if d == 0 or d == 1:
        s %= ((R - 1) * 2)
    else:
        s %= ((C - 1) * 2)
    board[r][c] = [s, d, z]

answer = 0
for i in range(C):
    answer += find_shark(i)
    board = move_shark(board)

print(answer)