[백준/BOJ] 19237: 어른 상어 (Python 파이썬)

1. 문제 

청소년 상어는 더욱 자라 어른 상어가 되었다. 상어가 사는 공간에 더 이상 물고기는 오지 않고 다른 상어들만이 남아있다. 상어에는 1 이상 M 이하의 자연수 번호가 붙어 있고, 모든 번호는 서로 다르다. 상어들은 영역을 사수하기 위해 다른 상어들을 쫓아내려고 하는데, 1의 번호를 가진 어른 상어는 가장 강력해서 나머지 모두를 쫓아낼 수 있다.

N×N 크기의 격자 중 M개의 칸에 상어가 한 마리씩 들어 있다. 맨 처음에는 모든 상어가 자신의 위치에 자신의 냄새를 뿌린다. 그 후 1초마다 모든 상어가 동시에 상하좌우로 인접한 칸 중 하나로 이동하고, 자신의 냄새를 그 칸에 뿌린다. 냄새는 상어가 k번 이동하고 나면 사라진다.

 

각 상어가 이동 방향을 결정할 때는, 먼저 인접한 칸 중 아무 냄새가 없는 칸의 방향으로 잡는다. 그런 칸이 없으면 자신의 냄새가 있는 칸의 방향으로 잡는다. 이때 가능한 칸이 여러 개일 수 있는데, 그 경우에는 특정한 우선순위를 따른다. 우선순위는 상어마다 다를 수 있고, 같은 상어라도 현재 상어가 보고 있는 방향에 따라 또 다를 수 있다. 상어가 맨 처음에 보고 있는 방향은 입력으로 주어지고, 그 후에는 방금 이동한 방향이 보고 있는 방향이 된다.

 

모든 상어가 이동한 후 한 칸에 여러 마리의 상어가 남아 있으면, 가장 작은 번호를 가진 상어를 제외하고 모두 격자 밖으로 쫓겨난다.

 

이 과정을 반복할 때, 1번 상어만 격자에 남게 되기까지 몇 초가 걸리는지를 구하는 프로그램을 작성하시오.

 

2. 입력 

첫 줄에는 N, M, k가 주어진다. (2 ≤ N ≤ 20, 2 ≤ M ≤ N2, 1 ≤ k ≤ 1,000)

그 다음 줄부터 N개의 줄에 걸쳐 격자의 모습이 주어진다. 0은 빈칸이고, 0이 아닌 수 x는 x번 상어가 들어있는 칸을 의미한다.

 

그 다음 줄에는 각 상어의 방향이 차례대로 주어진다. 1, 2, 3, 4는 각각 위, 아래, 왼쪽, 오른쪽을 의미한다.

그 다음 줄부터 각 상어의 방향 우선순위가 상어 당 4줄씩 차례대로 주어진다. 각 줄은 4개의 수로 이루어져 있다. 하나의 상어를 나타내는 네 줄 중 첫 번째 줄은 해당 상어가 위를 향할 때의 방향 우선순위, 두 번째 줄은 아래를 향할 때의 우선순위, 세 번째 줄은 왼쪽을 향할 때의 우선순위, 네 번째 줄은 오른쪽을 향할 때의 우선순위이다. 각 우선순위에는 1부터 4까지의 자연수가 한 번씩 나타난다. 가장 먼저 나오는 방향이 최우선이다. 예를 들어, 우선순위가 1 3 2 4라면, 방향의 순서는 위, 왼쪽, 아래, 오른쪽이다.

 

맨 처음에는 각 상어마다 인접한 빈 칸이 존재한다. 따라서 처음부터 이동을 못 하는 경우는 없다.

 

3. 출력 

1번 상어만 격자에 남게 되기까지 걸리는 시간을 출력한다. 단, 1,000초가 넘어도 다른 상어가 격자에 남아 있으면 -1을 출력한다.

 

4. 해결방법 

구현, 시뮬레이션 문제이다. 문제의 조건에 맞게 구현하면 되는 문제이다.

우선, 크게 3단계로 나눠서 구현하였다. 

 

1. 냄새 남기기

    - 각 상어가 자신의 위치에 냄새를 남김

2. 상어 이동

    - 우선순위에 따라 빈칸 -> 자신 냄새 칸 우선 이동

    - 한 칸에 여러 상어가 겹치면, 작은 번호 상어만 생존

3. 냄새 감소

    - 시간 흐름에 따라 보드에서 냄새 시간 감소

 

5. 구현코드

n,m,k = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(n)]
d = list(map(int, input().split())) # 상어 방향
shark = [[] for _ in range(m)] #x,y,direction
priorities = [[] for _ in range(m)] #상어별 우선순위

#방향 (위,아래,왼,오)
dx = [-1,1,0,0]
dy = [0,0,-1,1]

for i in range(m):
    for _ in range(4): #상어 우선순위 저장
        priorities[i].append(list(map(int, input().split())))

for i in range(n):
    for j in range(n):
        if board[i][j]:
            shark[board[i][j]-1] = [i,j,d[board[i][j]-1]-1] #x,y,direction
        board[i][j] = [0,0]  # 냄새 정보로 초기화 [냄새 시간, 상어 번호]

def smell(board,shark): #냄새 남기기: 각 상어의 현재 위치에 자신의 냄새 남김
    for i in range(len(shark)):
        if shark[i]:
            x,y,d = shark[i]
            board[x][y] = [k,i] #k시간, 상어번호
    return board

def next(board): #냄새 1초 줄이기
    for i in range(n):
        for j in range(n):
            if board[i][j][0] > 0:
                board[i][j][0] -= 1
    return board

def move(shark):
    tmp = [[[] for _ in range(n)] for _ in range(n)] ## 이동 결과 (여러 상어가 겹치는지 판단)

    for i in range(len(shark)):
        if shark[i]:
            x,y,d = shark[i]
            candidate = [] #빈 칸 후보
            my_candidate = [] #내 냄새가 있는 칸 후보

            # 4 방향 확인
            for q in range(4):
                nx, ny = x + dx[q], y + dy[q]
                if 0<=nx<n and 0<=ny<n:
                    if board[nx][ny][0] == 0: #빈 칸
                        candidate.append((nx,ny,q))
                    elif board[nx][ny][1] == i : #내 냄새
                        my_candidate.append((nx,ny,q))

            new_d = d # 상어 다음 방향
            if not candidate:
                candidate = my_candidate #빈 칸이 없으면 내 냄새로 이동

            # 후보 중 우선순위 고려해서 이동 방향 선택
            if len(candidate) >= 2:
                shark_prioi = priorities[i][d] # 현재 방향에 대한 우선순위 리스트
                for prioi in shark_prioi:
                    for nx,ny,q in candidate:
                        flag = False
                        if prioi-1 == q: #우선순위와 일치하면
                            new_d = prioi-1
                            flag = True
                            break
                    if flag:
                        break
            else:
                new_d = candidate[0][2]

            # 상어 정보 업데이트 및 이동 결과 저장
            shark[i] = [x+dx[new_d],y+dy[new_d], new_d]
            tmp[x+dx[new_d]][y+dy[new_d]].append(i)

        # 겹치는 상어 정리 (번호가 작은 상어만 생존)
        for i in range(n):
            for j in range(n):
                if len(tmp[i][j]) > 1:
                    tmp[i][j].sort()
                    for loser in tmp[i][j][1:]:
                        shark[loser] = []

        # 살아있는 상어 수 카운트
        cnt = sum(1 for i in range(m) if shark[i])

    return shark, cnt

for t in range(1000):
    board = smell(board,shark) #현재 상어 위치에 냄새 남김
    shark, live = move(shark) #상어 이동
    board= next(board) #냄새 1초 줄이기

    if live == 1:  # 상어가 1마리만 남았을 때 종료
        print(t+1)
        break

else:
    print(-1)