[백준] 19237번 - 어른 상어 (파이썬)

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

# 어른 상어
import copy
import sys
input = sys.stdin.readline

N, M, k = map(int, input().split())
arr = []
shark = []
history = [[0] * N for _ in range(N)]
history_index = []
for i in range(N):
    arr.append(list(map(int, input().split())))
    for j in range(N):
        if arr[i][j] != 0:
            arr[i][j] = arr[i][j]
            history[i][j] = k
            history_index.append((i, j))
            shark.append([arr[i][j], i, j])

shark_dir = [0]+list(map(int, input().split()))
for i in range(len(shark)):
    shark[i].append(shark_dir[arr[shark[i][1]][shark[i][2]]])

dx = [0, -1, 1, 0, 0]
dy = [0, 0, 0, -1, 1]

shark_move_priority = [[]]
for _ in range(M):
    temp = [[]]
    for _ in range(4):
        temp.append(list(map(int, input().split())))
    shark_move_priority.append(temp)


def move_shark(temp):
    global M
    for i in range(len(shark)):
        # 쫒겨난 상어는 continue
        if shark[i] == [0, 0, 0, 0]:
            continue
        shark_num, x, y, dir = shark[i]
        isMoved = False
        # 빈공간으로 이동
        for ndir in shark_move_priority[shark_num][dir]:
            nx = x + dx[ndir]
            ny = y + dy[ndir]
            if 0 <= nx < N and 0 <= ny < N:
                if temp[nx][ny] == 0:
                    # 해당 공간에 다른 상어가 있다면
                    if arr[nx][ny] != 0:
                        M -= 1
                        # 두 상어의 크기를 비교해서 현재 상어가 더 쎄다면
                        if fight_shark(nx, ny, x, y):
                            for j in range(len(shark)):
                                num, _, _, _ = shark[j]
                                if num == arr[nx][ny]:
                                    shark[j] = [0, 0, 0, 0]
                                    break
                            arr[nx][ny] = shark_num
                            shark[i] = [shark_num, nx, ny, ndir]
                            update_history(nx, ny)
                            isMoved = True
                            break
                        # 현재 상어가 더 약하다면
                        else:
                            shark[i] = [0, 0, 0, 0]
                            isMoved = True
                            break
                    # 혼자만 해당 공간으로 이동했다면
                    else:
                        arr[nx][ny] = shark_num
                        shark[i] = [shark_num, nx, ny, ndir]
                        update_history(nx, ny)
                        isMoved = True
                        break
        # 빈공간이 없어서 이동을 못한 경우, 자기 채취가 있는 곳으로 이동
        if not isMoved:
            for ndir in shark_move_priority[shark_num][dir]:
                nx = x + dx[ndir]
                ny = y + dy[ndir]
                if 0 <= nx < N and 0 <= ny < N:
                    if temp[nx][ny] == shark_num:
                        arr[nx][ny] = shark_num
                        shark[i] = [shark_num, nx, ny, ndir]
                        update_history(nx, ny)
                        break


def fight_shark(x, y, a, b):
    if arr[x][y] > arr[a][b]:
        return True
    else:
        return False


def update_history(x, y):
    if (x, y) in history_index:
        history[x][y] = k+1
    else:
        history_index.append((x, y))
        history[x][y] = k+1


move = 0
while M != 1:
    if move > 1000:
        break
    # 이동
    temp = copy.deepcopy(arr)
    move_shark(temp)
    # 채취 지우기
    for i, j in history_index:
        if history[i][j] == 0:
            continue
        history[i][j] -= 1
        if history[i][j] == 0:
            arr[i][j] = 0
    move += 1
print(-1 if move > 1000 else move)

 

구현(시물레이션)
1.  arr : 현재 상어들의 상황 판, history : 상어들의 채취의 남은 시간, history_index : 상어들의 채취가 있는 위치
    shark : 상어들의 정보 (상어 번호, x위치, y 위치, 방향), shark_move_priority : 상어의 방향 우선순위 등을 입력받는다.
2. 상어가 한마리 남을 때까지 while문
    - move_shark : 상어의 이동
        - shark_fight : 더 센 상어인지 아닌지 bool값 반환
        - update_history : history_index에 있는 값은 k+1로 업데이트만, 없으면 history_index에도 추가
    - 채취 지우기 : history_index를 완전탐색하면서 1씩 빼가고 0일 경우 arr[i][j]를 0으로 초기화
3. 이동 시간이 1000보다 크다면 -1 아니면 move 출력

 

너무 복잡하게 푼 것 같다. 빠르게 풀기위해서 처음 떠오른 아이디어를 바로 구현해서 풀었다.

지금 생각해보면 훨씬 쉬운 방법이 있는데 시간을 너무 의식한 것 같다.

다음엔 최적의 알고리즘을 좀 더 생각해서 실코딩 시간을 줄여봐야겠다.

 

이전에 풀었던 문제와 이어지는 스토리가 있는 문제이다.

[백준] 16236번 - 아기 상어

[백준] 16236번 - 아기 상어 (파이썬)

[백준] 19236번 - 청소년 상어

[백준] 19236번 - 청소년 상어 (파이썬)