136. [삼성기출32]Python 백준 19237 번 어른 상어

 

안녕하세요 코딩하는 덕구입니다.

백준 19237 어른 상어입니다.

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

19237번: 어른 상어

백준 19237 어른 상어 정답코드 입니다. 설명은 아래에 있습니다.

 

N, M, K = map(int, input().split())
board = [[[0, 0] for _ in range(N)] for _ in range(N)]
sharks = [0 for _ in range(M + 1)]
smells = []
prior = [[[]] for _ in range(M + 1)]
dx = [0, -1, 1, 0, 0]
dy = [0, 0, 0, -1, 1]
for i in range(N):
    tmp = list(map(int, input().split()))
    for j in range(N):
        if tmp[j] != 0:
            board[i][j] = [tmp[j], K]
            sharks[tmp[j]] = [i, j, 0]
            smells.append([i, j])

shark_direction = list(map(int, input().split()))

for i, s in enumerate(shark_direction):
    sharks[i + 1][2] = s

for i in range(M):
    for j in range(4):
        prior[i + 1].append(list(map(int, input().split())))


def debug():
    for i in range(N):
        for j in range(N):
            print(board[i][j], end=" ")
        print()
    print()

def move():
    global M
    for i in range(1, len(sharks)):
        if sharks[i] != 0:
            x, y, d = sharks[i]
            for j in range(4):
                nd = prior[i][d][j]
                nx, ny = dx[nd] + x, dy[nd] + y
                if 0 <= nx < N and 0 <= ny < N:
                    if board[nx][ny] == [0, 0]:
                        board[nx][ny][0] = i
                        smells.append([nx, ny])
                        sharks[i] = [nx, ny, nd]
                        break

                    elif board[nx][ny][1] == 0:
                        sharks[i] = 0
                        M -= 1
                        break

            if sharks[i] != 0:
                if [x, y, d] == sharks[i]:
                    for j in range(4):
                        nd = prior[i][d][j]
                        nx, ny = dx[nd] + x, dy[nd] + y
                        if 0 <= nx < N and 0 <= ny < N:
                            if board[nx][ny][0] == i:
                                sharks[i] = [nx, ny, nd]
                                break

def spread_smell():
    for s in sharks:
        if s != 0:
            x, y, _ = s
            board[x][y][1] = K + 1

def reduce_smell():
    global smells
    tmp = []
    for s in smells:
        x, y = s
        board[x][y][1] -= 1
        if board[x][y][1] != 0:
            tmp.append([x, y])
        else:
            board[x][y] = [0, 0]
        smells = tmp

def solve():
    for cnt in range(1, 1001):
        move()
        spread_smell()
        reduce_smell()
        if M == 1:
            return cnt
    return -1

print(solve())

 

문제 접근

상어를 우선순위에 맞춰 이동시키는 함수 move()

이동한 자리에 냄새를 뿌리는 함수 spread_smell()

모든 냄새를 1씩 줄여주는 함수 reduce_smell()

3개의 함수를 1초에 각각 1번씩 실행시킨 후 총 상어의 개수를 확인합니다.

상어가 1마리 남았다면 종료하고 시간을 return해줍니다.

 

Python 코드 구현

상어의 방향, 격자의 상태, 이동 우선순위, 상어의 좌표를 저장합니다.

N, M, K = map(int, input().split())
board = [[[0, 0] for _ in range(N)] for _ in range(N)]
sharks = [0 for _ in range(M + 1)]
smells = []
prior = [[[]] for _ in range(M + 1)]
dx = [0, -1, 1, 0, 0]
dy = [0, 0, 0, -1, 1]
for i in range(N):
    tmp = list(map(int, input().split()))
    for j in range(N):
        if tmp[j] != 0:
            board[i][j] = [tmp[j], K]
            sharks[tmp[j]] = [i, j, 0]
            smells.append([i, j])

shark_direction = list(map(int, input().split()))

for i, s in enumerate(shark_direction):
    sharks[i + 1][2] = s

for i in range(M):
    for j in range(4):
        prior[i + 1].append(list(map(int, input().split())))

 

 

def solve():
    for cnt in range(1, 1001):
        move()
        spread_smell()
        reduce_smell()
        if M == 1:
            return cnt
    return -1

 

핵심 코드인 move() 입니다.

1. 숫자가 작은 상어부터 우선순위에 맞는 방향의 빈칸을 찾고 빈칸이 있다면 이동합니다.

이때 다른 상어가 들어와 있다면 먼저 들어온 상어의 숫자가 작으므로 나중에 들어온 상어는 쫒겨납니다.

 

2. 빈칸이 없다면 우선순위에 맞춰 본인의 냄새가 있는 곳으로 이동합니다.

냄새가 있는 곳으로 다른 상어는 이동하지 못하므로 현재 상어는 적어도 방금 전에서 이동한 한 칸의 자리를 갖게 됩니다.

따라서 냄새가 없는 경우는 존재하지 않습니다.

def move():
    global M
    for i in range(1, len(sharks)):
        if sharks[i] != 0:
            x, y, d = sharks[i]
            for j in range(4):
                nd = prior[i][d][j]
                nx, ny = dx[nd] + x, dy[nd] + y
                if 0 <= nx < N and 0 <= ny < N:
                    if board[nx][ny] == [0, 0]:
                        board[nx][ny][0] = i
                        smells.append([nx, ny])
                        sharks[i] = [nx, ny, nd]
                        break

                    elif board[nx][ny][1] == 0:
                        sharks[i] = 0
                        M -= 1
                        break

            if sharks[i] != 0:
                if [x, y, d] == sharks[i]:
                    for j in range(4):
                        nd = prior[i][d][j]
                        nx, ny = dx[nd] + x, dy[nd] + y
                        if 0 <= nx < N and 0 <= ny < N:
                            if board[nx][ny][0] == i:
                                sharks[i] = [nx, ny, nd]
                                break

 

 move()에서 저장한 상어의 좌표를 통해 현재 위치에 냄새를 뿌립니다.

구현의 편의를 위해 냄새는 K + 1로 저장합니다.

def spread_smell():
    for s in sharks:
        if s != 0:
            x, y, _ = s
            board[x][y][1] = K + 1

 

냄새가 있는 모든 위치에서 1씩 제거해주고

만약 냄새가 0 이되면 상어의 흔적또한 지워줍니다. 

def reduce_smell():
    global smells
    tmp = []
    for s in smells:
        x, y = s
        board[x][y][1] -= 1
        if board[x][y][1] != 0:
            tmp.append([x, y])
        else:
            board[x][y] = [0, 0]
        smells = tmp

 

백준 19237 어른 상어 Python 코드였습니다.

감사합니다.