[BAEKJOON] 19237. 어른 상어

 

 

---

여러 사람들의 코드를 보면서 공부했다. 아직 시뮬레이션 문제는 너무 어려운 듯.

'''
조건
1. N: 공간 크기, M: 상어 번호, k: 냄새 지속 시간
2. 출력: 1번 상어만 남게 되기까지의 시간 (1,000초 이상 걸려도 안 끝나면 -1 출력)
[냄새 퍼뜨리기]
1. 냄새 1칸 이동할 때마다 -1
2. 상어가 있는 칸에 냄새 퍼뜨림
[이동]
1. 상하좌우 중 인접한 칸 중 하나로 이동
1-1. 아무 냄새가 없는 칸으로 이동
1-2. 그게 없으면 자신의 냄새가 있는 칸으로 이동
2. 한 칸에 여러 마리의 상어: 가장 작은 번호의 상어만 살아남음
'''

# 첫째 줄: N(공간의 크기), M(상어 번호), k(냄새 지속시간)
# 둘째 줄: 격자의 모습 (0: 빈칸 / 0이 아님: 상어 번호)
# 세번째 줄: 상어의 방향 (1: 위, 2: 아래, 3: 왼쪽, 4: 오른쪽)
# 네번째 줄~: 각 상어의 방향 우선순위 (위, 아래, 왼쪽, 오른쪽 순서)
N, M, k = map(int, input().split())
array = [list(map(int, input().split())) for _ in range(N)]
directions = list(map(int, input().split()))    # 현재 바라보는 방향(인덱스 0: 1번 상어 ~~)
smell = [[[0,0] for _ in range(N)] for _ in range(N)]        # 격자 베이스로 만든다 [0: 상어의 번호 / 1: 냄새 지속 시간]

# [
# [1번 상어: 위], [1번 상어: 아래], ...
# [2번 상어: 위], [2번 상어: 아래], ...
# ...]
priority_direction = [[] for _ in range(M)]     # 행: 상어 번호, 열: 바라보는 방향
for i in range(M):
    for j in range(4):
        priority_direction[i].append(list(map(int, input().split())))

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

# 냄새 업데이트하는 함수
def update_smell():
    for i in range(N):
        for j in range(N):
            # 만약 그 자리에 냄새가 있다면 -1 해주기
            if smell[i][j][1] > 0:
                smell[i][j][1] -= 1
            # 만약 그 자리에 상어가 있으면, 상어 냄새 퍼뜨리기
            if array[i][j] != 0:
                smell[i][j] = [array[i][j], k]

# 상어 다 이동시키는 함수
def move():
    # 시행 결과를 따로 저장하기 위한 격자 만들기
    new_array = [[0] * N for _ in range(N)]
    # 자리를 하나씩 확인해서 상어가 있으면 이동 시작하기
    for x in range(N):
        for y in range(N):
            if array[x][y] != 0:
                direction = directions[array[x][y] - 1]     # ?번 상어가 바라보는 위치
                found = False

                # 1. 아무 냄새가 없는 칸으로 이동
                # -> 일단 다음에 바라볼 방향 바꿔주기
                # -> 1) 상어가 없으면 그냥 자리 들어가기
                # -> 2) 상어가 있으면 번호 작은 상어가 살아남음
                for index in range(4):
                    nx = x + dx[priority_direction[array[x][y]-1][direction-1][index] - 1]
                    ny = y + dy[priority_direction[array[x][y]-1][direction-1][index] - 1]

                    if 0 <= nx < N and 0 <= ny < N:
                        if smell[nx][ny][1] == 0:
                            directions[array[x][y] - 1] = priority_direction[array[x][y]-1][direction-1][index]
                            if new_array[nx][ny] == 0:  # 상어가 없어서 그냥 들어갈 수 있음
                                new_array[nx][ny] = array[x][y]
                            else:   # 상어끼리 충돌
                                new_array[nx][ny] = min(array[x][y], new_array[nx][ny])
                            found = True
                            break       # 우선순위에 따라 자리 찾으면 바로 stop해야함
                if found:
                    continue    # 그 다음 번호의 상어 이동시키기

                # 2. 주변에 냄새가 모두 남아있으면 => 본인 냄새 있는 곳으로 이동
                for index in range(4):
                    nx = x + dx[priority_direction[array[x][y]-1][direction-1][index] - 1]
                    ny = y + dy[priority_direction[array[x][y]-1][direction-1][index] - 1]

                    if 0 <= nx < N and 0 <= ny < N:
                        # 자신의 냄새일 경우
                        if smell[nx][ny][0] == array[x][y]:
                            directions[array[x][y]-1] = priority_direction[array[x][y]-1][direction-1][index]
                            new_array[nx][ny] = array[x][y]
                            break       # 자기 냄새 찾자마자 바로 스탑 (여기서는 상어끼리 충돌할 일이 없음)
    
    return new_array        

time = 0
while True:
    update_smell()
    new_array = move()
    array = new_array
    time += 1

    one_check = True
    for i in range(N):
        for j in range(N):
            if array[i][j] > 1:
                one_check = False

    if one_check:   # 1번만 남았으면
        print(time)
        break

    if time >= 1000:
        print(-1)
        break