[BOJ]17143. 낚시왕

Posted Dec 28, 2021 Updated Dec 28, 2021

By your_full_name 16 min read

17143. 낚시왕

❌code1

  
import sys


def fish(c):
    weight = 0  # 상어 무게
    for r in range(1, R + 1):
        # 가장 가까운 곳에 있는 상어를 찾음
        if shark_map[r][c]:
            weight = shark_map[r][c]
            shark_map[r][c] = 0  # 상어의 위치를 삭제
            eaten_shark.add(weight)  # 먹힌 상어에 추가
            break
    return weight


def move(r, c, s, d, z):
    nr, nc = r, c
    if dr[d]:  # row 방향으로 움직이는 경우
        # 반복되는 위치 제거
        move_cnt = (s - 1) % (2 * R - 2) + 1

        while move_cnt:
            nr += dr[d]  # 이동
            # 범위 밖으로 이동시 방향을 전환하고 다시 돌아옴
            if nr == 0 or nr == R + 1:
                d = 3 - d
                nr += 2 * dr[d]
            move_cnt -= 1

    else:  # col 방향으로 움직이는 경우
        # 반복되는 위치 제거
        move_cnt = (s - 1) % (2 * C - 2) + 1

        while move_cnt:
            nc += dc[d]  # 이동
            # 범위 밖으로 이동시 방향을 전환하고 다시 돌아옴
            if nc == 0 or nc == C + 1:
                d = 7 - d
                nc += 2 * dc[d]
            move_cnt -= 1

    sharks[z] = (nr, nc, s, d)  # 상어의 정보 갱신

    # 현재 좌표에 있는 상어 크기
    shark_in_there = shark_map[nr][nc]

    # 현재 좌표에 상어가 있는 경우
    if shark_in_there:
        # 더 큰 상어가 있는 곳으로 간 경우 먹힘
        if z < shark_map[nr][nc]:
            eaten_shark.add(z)
        else:  # 작은 상어가 있다면 먹음
            eaten_shark.add(shark_in_there)
            shark_map[nr][nc] = z
    else:  # 상어가 없는 경우
        shark_map[nr][nc] = z


R, C, M = map(int, sys.stdin.readline().split())

sharks = {}  # 크기를 key로 상어 정보를 저장
shark_map = [[0] * (C + 1) for _ in range(R + 1)]  # 상어 위치에 상어 크기 저장
for _ in range(M):
    row, col, speed, direction, size = map(int, sys.stdin.readline().split())
    sharks[size] = (row, col, speed, direction)
    shark_map[row][col] = size

dr = (0, -1, 1, 0, 0)  # 행 기준 상하우좌
dc = (0, 0, 0, 1, -1)  # 열 기준 상하우좌

current_col = 1  # 현재 사람이 선 열
ans = 0  # 최종 정답
eaten_shark = set()  # 먹힌 상어, 잡힌 상어 저장 세트
while current_col <= C:
    ans += fish(current_col)

    # 상어가 이동한 뒤의 위치를 저장
    shark_map = [[0] * (C + 1) for _ in range(R + 1)]
    for size, shark_info in sharks.items():
        if size in eaten_shark:  # 이미 먹힌 상어는 넘어감
            continue
        row, col, speed, direction = shark_info
        move(row, col, speed, direction, size)

    current_col += 1
print(ans)

시도

상어는 모두 고유의 크기를 갖는다. 따라서 상어의 정보는 크기를 key로 갖는 딕셔너리에 저장한다.
상어의 위치는 2차원 배열에 저장한다. 계산의 편의를 위해 상단과 좌측을 한 칸씩 늘렸다.
사람의 이동이 끝날 때까지 다음을 반복한다.
1. 사람이 fish() 함수로 낚시 행동을 진행한다. 낚인 상어는 따로 세트에 저장한다.
2. 상어가 move() 함수로 움직임을 진행한다. 상어 정보가 담긴 딕셔너리를 순회하며 움직임을 진행하고 매 움직임은 2차원 배열에 기록된다. 잡아먹힌 상어는 따로 세트에 저장한다.
3. 먹히거나 낚인 상어는 움직이지 않으며 배열에서 사라진다.

상어의 움직임은 일정 수를 기준으로 반복되는 형태이다. 이를 고려하여 반복되는 움직임을 제거해 움직임 횟수를 최소한으로 줄일 수 있다.

  
        # 반복되는 위치 제거
        move_cnt = (s - 1) % (2 * R - 2) + 1

상어는 범위 밖으로 움직인 경우 즉, 0 또는 R + 1 또는 C + 1에 도달한 경우 방향을 전환하고 그 방향으로 2칸 움직인다. 상어가 1 또는 R 또는 C에 도달하였을 때 방향을 전환하면 벽면에 도달한 뒤 멈추어도 방향을 전환한다. 아래 코드를 통해 이를 방지할 수 있다.

  
        while move_cnt:
            nr += dr[d]  # 이동
            # 범위 밖으로 이동시 방향을 전환하고 다시 돌아옴
            if nr == 0 or nr == R + 1:
                d = 3 - d
                nr += 2 * dr[d]
            move_cnt -= 1

문제

시간 초과.

⭕code2

  
import sys


def fish(c):
    weight = 0  # 상어 무게
    for r in range(1, R + 1):
        # 가장 가까운 곳에 있는 상어를 찾음
        if shark_map[r][c]:
            weight = shark_map[r][c]
            shark_map[r][c] = 0  # 상어의 위치를 삭제
            eaten_shark.add(weight)  # 먹힌 상어에 추가
            break
    return weight


def move(r, c, s, d, z):
    # 움직이는 행 또는 열을 결정하고 그에 따른 변수 설정
    if dr[d]:
        n, k, toggle = R, r, 3
        increasing_or_decreasing = dr[d]
    else:
        n, k, toggle = C, c, 7
        increasing_or_decreasing = dc[d]

    # 반복되는 움직임 제거
    move_cnt = (s - 1) % (2 * n - 2) + 1

    if 0 < increasing_or_decreasing:  # 좌표가 증가하는 경우
        # 좌표가 벽을 한 번도 만나지 않은 경우
        if move_cnt <= n - k:
            k += move_cnt
        # 좌표가 벽을 한 번 만나 방향을 바꾼 경우
        elif move_cnt <= (n - k) + (n - 1):
            d = toggle - d  # 방향 전환
            move_cnt -= n - k
            k = n - move_cnt
        # 좌표가 벽을 또 한 번 만나 방향을 또 바꾼 경우
        else:
            k = move_cnt - (2 * n - k - 1) + 1
    else:  # 좌표가 감소하는 경우
        # 좌표가 벽을 한 번도 만나지 않은 경우
        if move_cnt <= k - 1:
            k -= move_cnt
        # 좌표가 벽을 한 번 만나 방향을 바꾼 경우
        elif k - 1 < move_cnt <= (k - 1) + (n - 1):
            d = toggle - d
            move_cnt -= k - 1
            k = 1 + move_cnt
        # 좌표가 벽을 또 한 번 만나 방향을 또 바꾼 경우
        else:
            k = n - (move_cnt - (n + k - 2))

    if toggle == 3:  # 행을 움직인 경우
        nr, nc = k, c
    else:  # 열을 움직인 경우
        nr, nc = r, k

    sharks[z] = (nr, nc, s, d)  # 상어의 정보 갱신

    # 현재 좌표에 있는 상어 크기
    shark_in_there = shark_map[nr][nc]

    # 현재 좌표에 상어가 있는 경우
    if shark_in_there:
        # 더 큰 상어가 있는 곳으로 간 경우 먹힘
        if z < shark_map[nr][nc]:
            eaten_shark.add(z)
        else:  # 작은 상어가 있다면 먹음
            eaten_shark.add(shark_in_there)
            shark_map[nr][nc] = z
    else:  # 상어가 없는 경우
        shark_map[nr][nc] = z


R, C, M = map(int, sys.stdin.readline().split())

sharks = {}  # 크기를 key로 상어 정보를 저장
shark_map = [[0] * (C + 1) for _ in range(R + 1)]  # 상어 위치에 상어 크기 저장
for _ in range(M):
    row, col, speed, direction, size = map(int, sys.stdin.readline().split())
    sharks[size] = (row, col, speed, direction)
    shark_map[row][col] = size

dr = (0, -1, 1, 0, 0)  # 행 기준 상하우좌
dc = (0, 0, 0, 1, -1)  # 열 기준 상하우좌

current_col = 1  # 현재 사람이 선 열
ans = 0  # 최종 정답
eaten_shark = set()  # 먹힌 상어, 잡힌 상어 저장 세트
while current_col <= C:
    ans += fish(current_col)

    # 상어가 이동한 뒤의 위치를 저장
    shark_map = [[0] * (C + 1) for _ in range(R + 1)]
    for size, shark_info in sharks.items():
        if size in eaten_shark:  # 이미 먹힌 상어는 넘어감
            continue
        row, col, speed, direction = shark_info
        move(row, col, speed, direction, size)
    current_col += 1
print(ans)

시도

상어의 움직임은 한 칸씩 실제로 이동하는 대신 수식으로 계산될 수 있다.

좌표가 증가하는 방향으로 움직이는 경우 즉, 상에서 하 또는 좌에서 우로 움직이는 경우 increasing_or_decreasing > 0이고 상어의 움직임은 다음과 같이 표현될 수 있다.

상어가 좌표 k에 있을 때 먼저 우측으로 n-k개의 좌표를 이동한 후 벽을 만난다.
벽을 만난 후 방향 전환을 해 좌측으로 n-1개의 좌표를 이동한다.
다시 벽을 만나 방향을 바꾸고 우측으로 k-1개의 좌표를 이동한다.

이후 움직임은 반복되므로 계산될 필요 없다.

  
    # 반복되는 움직임 제거
    move_cnt = (s - 1) % (2 * n - 2) + 1

좌표가 감소하는 방향으로 움직이는 경우 즉, 하에서 상 또는 우에서 좌로 움직이는 경우 increasing_or_decreasing < 0이고 상어의 움직임은 다음과 같이 표현될 수 있다.

상어가 좌표 k에 있을 때 먼저 좌측으로 k-1개의 좌표를 이동한 후 벽을 만난다.
벽을 만난 후 방향 전환을 해 우측으로 n-1개의 좌표를 이동한다.
다시 벽을 만나 방향을 바꾸고 좌측으로 n-k개의 좌표를 이동한다.

이후 움직임은 반복되므로 계산될 필요 없다.

따라서 상어의 움직임은 세 번의 움직임으로 분리될 수 있으며 각각의 경우에 따른 좌표를 다음과 같이 구할 수 있다.

  
    # 좌표가 증가하는 경우
    if 0 < increasing_or_decreasing:
        # 좌표가 벽을 한 번도 만나지 않은 경우
        # 상어의 좌표는 move_cnt만큼 좌표가 증가하도록 움직인다.
        if move_cnt <= n - k:
            k += move_cnt

        # 좌표가 벽을 한 번 만나 방향을 바꾼 경우
        # 현재 움직일 수 있는 횟수에서 (n-k)만큼 제거한 뒤
        # n에서 감소하는 방향으로 남은 횟수만큼 이동한다.
        elif move_cnt <= (n - k) + (n - 1):
            d = toggle - d  # 방향 전환
            move_cnt -= n - k
            k = n - move_cnt

        # 좌표가 벽을 또 한 번 만나 방향을 또 바꾼 경우
        # 현재 움직일 수 있는 횟수에서 (n-k)와 (n-1)만큼 제거한 뒤
        # 1에서 증가하는 방향으로 남은 횟수만큼 이동한다.
        else:
            k = move_cnt - (2 * n - k - 1) + 1

    # 좌표가 감소하는 경우
    else:
        # 좌표가 벽을 한 번도 만나지 않은 경우
        # 상어의 좌표는 move_cnt만큼 좌표가 감소하도록 움직인다.
        if move_cnt <= k - 1:
            k -= move_cnt

        # 좌표가 벽을 한 번 만나 방향을 바꾼 경우
        # 현재 움직일 수 있는 횟수에서 (k-1)만큼 제거한 뒤
        # 1에서 증가하는 방향으로 남은 횟수만큼 이동한다.
        elif k - 1 < move_cnt <= (k - 1) + (n - 1):
            d = toggle - d
            move_cnt -= k - 1
            k = 1 + move_cnt

        # 좌표가 벽을 또 한 번 만나 방향을 또 바꾼 경우
        # 현재 움직일 수 있는 횟수에서 (k-1)과 (n-1)만큼 제거한 뒤
        # n에서 감소하는 방향으로 남은 횟수만큼 이동한다.
        else:
            k = n - (move_cnt - (n + k - 2))

요약

반복적인 움직임을 보이는 경우 수식을 설정하여 최종 위치를 구할 수 있다.

Algorithm_problem_solving

BOJ

This post is licensed under CC BY 4.0 by the author.

❌code1

시도

문제

⭕code2

시도

요약

Trending Tags