[BOJ] 백준 19237번 문제 풀이 (Python)

1. 풀이

구현, 시뮬레이션 문제이다. 백준에 상어 시리즈로 올라운 문제 중 하나인데 문제를 제대로 읽지 못하고 구현을 해서 오래걸렸다. 구현, 시뮬레이션 문제는 주어진 조건에 맞춰 정확하게 구현을 하는 것이 시간을 단축하는 길인 것 같다. 괜히 어떻게든 코드를 줄여보겠다고 하는 순간 문제에서 의도하던대로 구현이 되지 않을 수 있다. 문제를 먼저 통과하고 코드를 줄이는 방향으로 하는 것이 구현, 시뮬레이션을 공부하는 방법인 것 같다.

주의할 점

1. 상어는 자신이 있는 곳에 냄새를 뿌린다.
   • K번 이동해야 냄새가 없어진다 → 즉, 이동 후 감소시켜야한다
2. 상어는 상하좌우로 움직일 수 있다.
   • 아무 냄새가 없는 칸을 먼저, 그 다음은 자신의 냄새가 있는 칸의 방향으로
   • 가능한 곳이 여러 곳일 때는 우선순위대로
3. 1칸에는 1마리의 상어만 존재할 수 있다
   • 여러마리가 있을 경우 번호가 가장 작은 상어만 살아남는다.
4. 1000초가 넘어도 다른 상어가 격자에 남아 있으면 -1을 출력한다.
   • 1000초를 포함한다는 뜻 (즉, 1000번 이동까지는 허용)

1번과 4번을 제대로 구현하지 못해서 시간이 너무 오래 걸렸다.

def bfs(smell_q):
    moved = {}
    q = {}
    
    for k in range(1,m+1):
        if k not in shark: continue
        y,x,d = shark[k]
        ny,nx,nd, n_smell = 0,0,0,-1
        for move_d in shark_move[k][d]:
            dy,dx = y + my[move_d], x + mx[move_d]
            if 0 <= dy < n and 0 <= dx < n:
                if (n_smell == -1  or n_smell == 1) and not visited[dy][dx]:
                    ny,nx,nd,n_smell = dy,dx,move_d, 0
                if n_smell == -1 and visited[dy][dx] == k:
                    ny,nx,nd,n_smell = dy,dx,move_d,1
        if (ny,nx) not in moved:
            shark[k] = (ny,nx,nd)
            moved[(ny,nx)] = k
        else:
            del shark[k]
            
    for i,j in smell_q:
        if smell_q[(i,j)] > 1:
            q[(i,j)] = smell_q[(i,j)] - 1
        else:
            visited[i][j] = 0

    for i,j in moved:
        visited[i][j] = moved[(i,j)]
        q[(i,j)] = K
    return q
        

n,m,K = map(int,input().split())
matrix = [list(map(int,input().split())) for _ in range(n)]
direction = [0] + list(map(int,input().split()))
shark_move= {}
for i in range(1,m+1):
    shark= {}
    for j in range(1,5):
        shark[j] = list(map(int,input().split()))
    shark_move[i] = shark
my = {1:-1,2:1,3:0,4:0}
mx = {1:0,2:0,3:-1,4:1}

visited = [[0] * n for _ in range(n)]
shark = {}
smell_q = {}

for i in range(n):
    for j in range(n):
        if matrix[i][j] != 0:
            shark[matrix[i][j]] = (i,j,direction[matrix[i][j]])
            visited[i][j] = matrix[i][j]
            smell_q[(i,j)]=K

possible = False
for c in range(1001):
    if len(shark) == 1:
        possible = True
        print(c)
        break
    smell_q = bfs(smell_q)

if not possible:
    print(-1)

백준에서 아기 상어, 청소년 상어 문제도 같이 보면 좋을 것 같다.