백준: 19237 어른 상어

문제

19237번: 어른 상어

 

문제 풀이

 상어의 위치와 상어의 방향이 주어진다. 이때 각 상어들은 이동하며 냄새를 뿌리고, 이동한다. 그리고 뿌려진 냄새는 K초가 지나면 사라진다. 이는 간단하게 생각하면 1) 냄새 뿌리기, 2) 상어 이동, 3) 시간에 따른 냄새 감소로 나누어 그대로 구현하면 된다.

 

 하지만 문제를 풀면서 3가지 문제를 맞이하며 푸는데 시간이 지연되었다.

• 동일한 자리에 여러 마리의 상어가 들어가는 경우, 가장 작은 번호를 가진 상어만 남는다.
  • 처음에는 동일한 자리의 경우 append를 해주면서 체크하거나 상어의 번호를 비교 연산을 통해 하나만 남도록 해볼 생각이었다.
  • 하지만, 가장 작은 번호를 가진 상어부터 우선적으로 처리하면, 알아서 처리될 일이다!
• 상, 하, 좌, 우의 우선순위를 오랜만에 주다 보니 x, y 수직선 좌표상으로 생각했다.
  • 뇌절이 왔는지, 행렬의 좌표가 아닌 x, y 좌표 상으로 생각하고 `dirs = ((0, -1), (0, 1), (-1, 0), (1, 0))`으로 초기화해두고 문제에 접근하고 있었다. 옳은 답이 안 나올 수밖에...😫
• 내가 3차원 배열로 설계를 하고, 각 인덱스에 대한 정보를 착각 하여 디버깅하는데 시간을 쓰고 있었다...

 

코드

from sys import stdin


SHARK, SCENT = 0, 1


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


def simulation():
    # 냄새 뿌리기.
    for s_idx, values in enumerate(sharks):
        if values is None:
            continue

        r, c, _ = values
        # 냄새를 뿌릴 수 있는 경우.
        if board[r][c] is None or board[r][c][SHARK] == s_idx:
            board[r][c] = [s_idx, K]
        else:
            sharks[s_idx] = None

    # 상어 이동
    for s_idx, values in enumerate(sharks):
        if values is None:
            continue

        r, c, cur_dir = values

        # 빈칸으로 이동 가능한 경우
        for next_dir in priority[s_idx][cur_dir]:
            dr, dc = dirs[next_dir]
            next_r, next_c = r + dr, c + dc

            if visitable(next_r, next_c) and board[next_r][next_c] is None:
                sharks[s_idx] = [next_r, next_c, next_dir]
                break
        # 자신의 냄새가 있는 칸으로 이동 가능한 경우
        else:
            for next_dir in priority[s_idx][cur_dir]:
                dr, dc = dirs[next_dir]
                next_r, next_c = r + dr, c + dc

                if visitable(next_r, next_c) and board[next_r][next_c][SHARK] == s_idx:
                    sharks[s_idx] = [next_r, next_c, next_dir]
                    break
            # 위의 2가지가 아니라면 이동 불가.
            else:
                sharks[s_idx] = None

    # 냄새 감소
    for r in range(N):
        for c in range(N):
            if board[r][c] is None:
                continue

            board[r][c][SCENT] -= 1

            if board[r][c][SCENT] == 0:
                board[r][c] = None


if __name__ == "__main__":
    dirs = ((-1, 0), (1, 0), (0, -1), (0, 1))
    N, M, K = map(int, stdin.readline().split())
    board = [list(map(int, stdin.readline().split())) for _ in range(N)]
    cur_shark_dirs = list(map(int, stdin.readline().split()))  # 각 상어의 방향
    sharks = [0] * M

    for i in range(N):
        for j in range(N):
            if board[i][j] != 0:
                # 위치, 방향을 인덱스에 맞게 감소
                sharks[board[i][j] - 1] = [i, j, cur_shark_dirs[board[i][j] - 1] - 1]
                board[i][j] -= 1
            board[i][j] = None

    priority = [[[0] for _ in range(4)] for _ in range(M)]

    for shark_idx in range(M):
        for p_idx in range(4):
            # 우선 순위 방향을 dirs 인덱스에 맞게 감소
            priority[shark_idx][p_idx] = [p - 1 for p in list(map(int, stdin.readline().split()))]

    for cur_time in range(-1, 1001):
        # 1번 상어만 남는 경우
        if sharks.count(None) == M - 1:
            print(cur_time)
            exit(0)
        else:
            simulation()
    else:
        print(-1)