백준: 17143 낚시왕

문제

17143번: 낚시왕

 

문제 풀이

 문제 요구 사항에 따라 순차적으로 구현하면 맞을 수 있는 문제이다. 낚시왕이 물고기를 잡고, 상어가 움직이는 것을 순차적으로 실행하면 문제에서 요구하는 답을 찾을 수 있다.

 

• 낚시왕이 `c + 1`, 즉 열을 한 칸 이동하여 해당 열 중 가장 땅과 가까운 행의 인덱스가 낮은 상어부터 잡게 된다.
  • 잡은 상어는 사라지게 된다.
• 1초 동안 상어가 이동한다.
  • 상어는 각각 1초에 이동할 수 있는 거리를 가지게 된다. 따라서 속도가 5라면 5칸 움직일 수 있다.
  • 상어가 움직이는 중 격자판을 벗어난다면, 진행 방향을 반대로 바꾼 후 움직인다.
    • `상 → 하`, `하 → 상`, `좌 → 우`, `우 → 좌`로 변경한다.
    • 동일한 위치에 상어가 존재한다면, 크기가 큰 상어가 작은 상어를 잡아먹는다.
• 낚시왕이 모든 열의 상어를 다 잡을 때까지, 위의 과정을 반복한 후 잡은 상어 크기의 합을 반환한다.

 

코드

from sys import stdin


def visitable(x, y):
    return 0 <= x < r and 0 <= y < c


def catch_shark(cur_loc):
    for x in range(r):
        if graph[x][cur_loc]:
            size = graph[x][cur_loc][SIZE]
            # 상어를 잡았으면 정보 삭제.
            graph[x][cur_loc] = 0
            return size
    return 0


def switch_dir(cur_dir):
    if cur_dir == 0:
        return 1
    elif cur_dir == 1:
        return 0
    elif cur_dir == 2:
        return 3
    return 2


def move_shark():
    next_graph = [[0] * c for _ in range(r)]

    for x in range(r):
        for y in range(c):

            if not graph[x][y]:
                continue

            next_x, next_y, cur_speed, cur_dir, cur_size = x, y, *graph[x][y]

            # speed 만큼 이동하도록 함.
            # speed에 한번에 위치를 찾도록 하면, Python으로도 통과할 수 있다.
            while cur_speed > 0:
                dx, dy = dirs[cur_dir]
                next_x += dx
                next_y += dy
                # 방문 가능하다면, 이동 가능한 횟수 감소
                if visitable(next_x, next_y):
                    cur_speed -= 1
                # 방문이 불가능하다면, 뒤로 가며 경로 변경
                else:
                    next_x -= dx
                    next_y -= dy
                    cur_dir = switch_dir(cur_dir)
                    graph[x][y][DIRECTION] = cur_dir
            # 현재 위치에 상어가 없는 경우.
            if not next_graph[next_x][next_y]:
                next_graph[next_x][next_y] = graph[x][y]
            # 상어가 있다면 크기를 비교하여, 갱신함
            elif next_graph[next_x][next_y][SIZE] < cur_size:
                next_graph[next_x][next_y] = graph[x][y]

    return next_graph

if __name__ == "__main__":
    SPEED, DIRECTION, SIZE = 0, 1, 2
    dirs = ((-1, 0), (1, 0), (0, 1), (0, -1))
    r, c, m = map(int, stdin.readline().split())
    graph = [[0] * c for _ in range(r)]
    answer = 0

    for _ in range(m):
        i, j, s, d, z = map(int, stdin.readline().split())
        # d는 인덱스에 맞게 - 1
        graph[i - 1][j - 1] = [s, d - 1, z]

    for loc in range(c):
        # 상어를 잡음
        answer += catch_shark(loc)
        # 상어를 이동 시킴
        graph = move_shark()

    print(answer)

 상어의 다음 위치를 찾기 위해 `while`문을 통해 반복하여 찾으므로, `Python`의 경우 시간 초과가 발생한다.😢 하지만 `PyPy3`로는 통과할 수 있다. 상어가 방향을 찾을 때 한 번에 찾을 수 있도록 하면 `Python`으로도 시간 내에 통과가 가능하다.