19237-어른상어

www.acmicpc.net/problem/19237

1. 모든 냄새 업데이트

2. 모든 상어들을 조건에 맞게 이동

   1. 냄새가 존재하지 않는 곳을 우선순위에 따라 탐색

   2. 자신의 냄새를 우선순위에 따라 탐색

3. 시간 추가

4. 1번 상어만 남았다면 시간 출력

5. 1,000 초가 지났다면 -1 출력

n, m, k = map(int,input().split())

# 모든 상어의 위치를 포함하는 2차원 리스트
array = []
for i in range(n):
    array.append(list(map(int, input().split())))

# 모든 상어의 현재 방향 정보
directions = list(map(int, input().split()))

# 각 위치마다 [특정 냄새의 상어 번호, 특정 냄새의 남은시간]을 저정하는 2차원 리스트
smell = [[[0, 0]] * n for _ in range(n)]

# 각 상어의 회정 방향 우선 순위 정보
priorities = [[] for _ in range(m)]
for i in range(m):
    for j in range(4):
        priorities[i].append(list(map(int, input().split())))

# 특정 위치에서 이동 가능한 4가지 방향
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
            # 상어가 존재한다면 해당 위치 냄세 k 로 설정
            if array[i][j] != 0:
                smell[i][j] = [array[i][j], k]
                '''냄새로 그냥 상어번호와 방향정보 있는 리스트랑 냄새 넣어버리기'''
''''''''''''''''''''''''''''''''''''''''''
def move():
    # 이동 결과를 담기 위해 임시 결과 테이블을 초기화하자
    # 새로 작성할 arr 은 비어있어야 한다..! 그래야 기존의 arr 가 남지 않으니
    # 그로 인해 이동된 상어만 할당해주면 된다.
    new_array = [[0] * n for _ in range(n)]
    # 모든 위치 확인
    for x in range(n):
        for y in range(n):
            # 기존 arr 에 상어가 있다면
            if array[x][y] != 0:
                # 현재 상어의 방향을 변수로 잡아주자 !! 필요하니까 !!
                direction = directions[array[x][y] - 1]

                # 우선 냄새가 존재하지 않는 곳이 있는지 확인하자
                # 여기서 확인하는 순서가 중요하다.
                    # 현재 상어번호에 해당하는 인덱스 들어가서,
                        # 현재 상어의 방향에 해당하는 인덱스 들어가서,
                            # 순서대로 0~3 까지 순서대로 -> 반복문
                                # 그럼 결과적으로 1,2,3,4 방향을 찾는데 -1 해줘서 x 에 더해주자
                '''냄새가 존재하지 않는 곳을 찾았다면, 자신의 냄새가 있는 곳을 탐색할 필요 없으니 이를 if, continue 로 구현 '''
                found = False
                for index in range(4):
                    nx = x + dx[priorities[array[x][y] - 1][direction - 1][index] - 1]
                    ny = y + dy[priorities[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] = priorities[array[x][y] - 1][direction - 1][index]
                            # 이동하는데 만약 이미 다른 상어가 있다면
                            if new_array[nx][ny] != 0:
                                new_array[nx][ny] = min(new_array[nx][ny],array[x][y])
                            else:
                                new_array[nx][ny] = array[x][y]
                            '''여기 도달했다는 것은 냄새가 존재하지 않는 곳을 찾아 이동했다는 것이니'''
                            found = True
                            # 더 이상 냄새가 존재하지 않는 곳을 탐색할 필요 없으니
                            break
                '''냄새가 존재하지 않는 곳을 찾았었다면 이후 자신의 냄새를 찾지 않는다.'''
                if found:
                    continue
                # 냄새가 존재하지 않는 곳이 없으니 자신의 냄새 찾자
                # 여기서도 확인하는 순서가 중요하다.
                    # 현재 상어번호에 해당하는 인덱스 들어가서,
                        # 현재 상어의 방향에 해당하는 인덱스 들어가서,
                            # 순서대로 0~3 까지 순서대로 -> 반복문
                                # 그럼 결과적으로 1,2,3,4 방향을 찾는데 -1 해줘서 x 에 더해주자
                for index in range(4):
                    nx = x + dx[priorities[array[x][y] - 1][direction - 1][index] - 1]
                    ny = y + dy[priorities[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] = priorities[array[x][y] - 1][direction - 1][index]
                            # 상어 이동
                            '''다른 상어가 있다면 자신의 냄새가 존재할 수 없다는 것을 인지하자'''
                            new_array[nx][ny] = array[x][y]
                            # 더이상 자신의 냄새가 있는 곳을 탐색할 필요가 없으니
                            break
    # 모든 상어에 대하여 이동을 완료했으니
    return new_array
''''''''''''''''''''''''''''''''''''
# 걸린시간
time = 0
while True:
    # 모든 곳 냄새 업데이트
    update_smell()
    # 모든 상어 이동시키기
    '''이렇게 arr 를 수정시키는 경우 새로운 arr 을 반환하는 함수를 넣자'''
    new_array = move()
    '''기존의 배열은 이동한 배열로 바꿔주자'''
    array = new_array
    time += 1

    # 1번 상어만 남았는지 체크
    check = True
    for i in range(n):
        for j in range(n):
            # 1보다 큰 상어가 존재한다면
            if array[i][j] > 1:
                # 1번 외의 상어가 존재하면 표시남겨줌
                check = False

    # 표시가 없다면
    if check:
        print(time)
        break

    # 1,000초가 지났다면
    if time >= 1000:
        print(-1)
        break