[백준] 19237번 어른 상어

24987 단어 구현구현

문제 링크

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

문제 설명

  • 상어들이 냄새를 풍기면서 돌아다님
  • 냄새가 없거나 자신의 냄새가 있거나.. 등 우선순위에 따라
  • 겹치면 숫자 작은 상어가 쫓아냄
  • 1만 남았을 경우 종료

풀이

  • board, 현재 위치, 현재 방향, 냄새를 따로 관리
  • 매 초마다
    • 체크
    • 이동
    • 쫓아내기
    • 냄새 갱신

코드

def move():
    for num in range(1, m+1):
        y, x = shark[num]
        if not (0 <= y < n) or not (0 <= x <n):
            continue
        positions = get_nothing(num, y, x, dirs[num])
        if not positions:
            positions = get_mine(num, y, x, dirs[num])
        if not positions:
            continue
        ny, nx, nd = positions[0]
        board[ny][nx].append(board[y][x].pop())
        dirs[num] = nd
        shark[num] = (ny, nx)


def get_mine(num, y, x, d):
    positions = []
    for nd in priority[num][d]:
        ny, nx = y + dy[nd], x + dx[nd]
        if 0 <= ny < n and 0 <= nx < n:
            if smell[ny][nx][0] == num:
                positions.append([ny, nx, nd])
    return positions


def get_nothing(num, y, x, d):
    positions = []
    for nd in priority[num][d]:
        ny, nx = y + dy[nd], x + dx[nd]
        if 0 <= ny < n and 0 <= nx < n:
            if smell[ny][nx][1] == 0:
                positions.append([ny, nx, nd])
    return positions


def out():
    for y in range(n):
        for x in range(n):
            if len(board[y][x]) >= 2:
                minn = min(board[y][x])
                for num in board[y][x]:
                    if num != minn:
                        shark[num] = (-1, -1)
                board[y][x] = [minn]


def spread():
    for y in range(n):
        for x in range(n):
            if smell[y][x][1] > 0:
                smell[y][x][1] -= 1
                if smell[y][x][1] == 0:
                    smell[y][x][0] = 0
            if board[y][x]:
                smell[y][x] = [board[y][x][0], k]

# init
import sys
read = sys.stdin.readline
n,m,k = map(int,read().split())
board = [[[] for _ in range(n)] for _ in range(n)]
smell = [[[0,0] for _ in range(n)] for _ in range(n)]
shark = [(-1, -1) for _ in range(m+1)]
for i in range(n):
    line = list(map(int, read().split()))
    for j in range(n):
        if line[j] > 0:
            shark[line[j]] = (i, j)
            board[i][j].append(line[j])
            smell[i][j] = [line[j], k]
dirs = [0] + list(map(int, read().split()))
priority = [[]]
for _ in range(m):
    tmp = [[]]
    for _ in range(4):
        tmp.append(list(map(int, read().split())))
    priority.append(tmp)
dy, dx = [0,-1,1,0,0], [0,0,0,-1,1]

# start
answer = -1
for t in range(1001):
    if len(set(shark)) == 2:
        answer = t
        break
    move()
    out()
    spread()
print(answer)

좋은 웹페이지 즐겨찾기