[백준/19237/파이썬] 어른 상어

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

19237번: 어른 상어

상어 시리즈가 엄청 많다.

Problem

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

조건

• N×N 크기의 격자 중 M개의 칸에 상어가 한 마리씩 들어 있다.
• 맨 처음에는 모든 상어가 자신의 위치에 자신의 냄새를 뿌린다. 그 후 1초마다 모든 상어가 동시에 상하좌우로 인접한 칸 중 하나로 이동하고, 자신의 냄새를 그 칸에 뿌린다. 냄새는 상어가 k번 이동하고 나면 사라진다.
• 각 상어가 이동 방향을 결정할 때는, 먼저 인접한 칸 중 아무 냄새가 없는 칸의 방향으로 잡는다.
• 그런 칸이 없으면 자신의 냄새가 있는 칸의 방향으로 잡는다.
• 이때 가능한 칸이 여러 개일 수 있는데, 그 경우에는 특정한 우선순위를 따른다.우선순위는 상어마다 다를 수 있고, 같은 상어라도 현재 상어가 보고 있는 방향에 따라 또 다를 수 있다. 상어가 맨 처음에 보고 있는 방향은 입력으로 주어지고, 그 후에는 방금 이동한 방향이 보고 있는 방향이 된다.
• 모든 상어가 이동한 후 한 칸에 여러 마리의 상어가 남아 있으면, 가장 작은 번호를 가진 상어를 제외하고 모두 격자 밖으로 쫓겨난다.
• 이 과정을 반복할 때, 1번 상어만 격자에 남게 되기까지 몇 초가 걸리는지를 구하는 프로그램을 작성하시오.단, 1,000초가 넘어도 다른 상어가 격자에 남아 있으면 -1을 출력한다.
• 첫 줄에는 N, M, k가 주어진다. (2 ≤ N ≤ 20, 2 ≤ M ≤ N2, 1 ≤ k ≤ 1,000),0은 빈칸이고, 0이 아닌 수 x는 x번 상어가 들어있는 칸을 의미한다.

SOL

워후, 구현량이 어마어마한 문제이다. 일단, shark에 대한 정보량이 매우 많고, 조건 사항도 주렁주렁 달려있는 문제이다. 천천히 정리를 일단 해보자.

 

입/출력 부분

상어

• 기본적으로, 어디에 위치해있는지 위치 정보를 갖고있어야한다.
• 상어의 크기(numbering)을 해야한다. 크기가 작은 상어일 수록 power가 쎄서, 다른 상어와 만났을 때, number가 작은 상어가 이긴다. (idx를 통해서 numbering해도될거같다)
• 상어의 머리방향(head)를 반영해야한다.

움직이는 우선순위

• 3차원 배열로 구현할거다. [상어번호][상,하,좌,우][0~3] 으로 구현할거임! 이때, 1,2,3,4가 상,하,좌,우에 맞게끔 dx,dy를 조정해줄거다. 
• 우선순위에 따라서, nd(향하는 방향)을 바꿔줄거임.

메인 로직 부분

상어가 동시에 움직인다.

• 상어가 1마리씩 따로 따로 움직이는게 아니라, 동시에 상어를 다 움직여 줘야한다. 그러므로, shark의 배열을 일단 한번 다 돌아서, 상어 움직여주고 -> 그뒤에 바뀐 정보를 반영하는 식으로 구현해야한다.
• 상어가 nd(향하는 방향)에 따라서, 빈칸이면 그냥가면 되고, 가는곳에 이미 상어가 있으면, 크기 비교를 통해서 탈락하는 상어를 반영해주면 됨! 
• 그리고, 주변에 빈칸이 없다면, 자신이 왔던 곳(냄새를 뿌렸던 곳)을 향해서 간다.

냄새 정보를 반영해줘야한다.

• 상어가 다 움직이고 나면, 냄새 정보들은 시간이 지날때마다 -1씩 되고, 0이 되면 그 칸은 다시 빈칸이 된다.

상어가 움직인 곳을 board에 반영해줘야한다.

• 상어가 움직여서, 다시 도착한 곳에 상어가 또 냄새를 뿌린다! 이 정보를 반영해줘야한다.

냄새정보 반영과 상어 움직인 곳을 update 하는건 하나로 묶어서 구현해도 상관 없을듯하다.

import sys
input= sys.stdin.readline
N,M,K = map(int,input().split())
dx=[0,0,0,-1,1]
dy=[0,-1,1,0,0]
board=[]
#shark[상어번호][0] = y, [1]=x,[2] = 향하고 있는 방향
shark=[[] for _ in range(M)]
for i in range(N):
    board.append(list(map(int,input().split())))
    for j in range(N):
        if board[i][j]: #상어가 있는 경우
            shark[board[i][j]-1].extend([i,j])
            board[i][j] =[board[i][j],K]

#상어의 현재 방향
shark_dir=list(map(int,input().split()))
for i in range(M):
    shark[i].append(shark_dir[i])
#print(shark)
#상어의 우선도
#shark[상어번호][상,하,좌,우][0~3]
shark_priority=[[] for _ in range(M)]
idx = -1
for i in range(4*M):
    if i%4==0:
        idx+=1
    shark_priority[idx].append(list(map(int,input().split())))

def is_valid_coord(ny,nx):
    return 0<=ny<N and 0<=nx<N

def update_smell():
    for i in range(N):
        for j in range(N):
            #상어가 있었던 곳은 1씩 빼준다.
            if board[i][j]:
                board[i][j][1] -=1
                if board[i][j][1] ==0:
                    board[i][j] =0
def update_shark():
    for i in range(M):
        if shark[i]:
            y,x,=shark[i][0],shark[i][1]
            board[y][x] = [i+1,K]

def set_direction(y,x,k):
    nd=shark_priority[i][d-1][k]
    ny=y+dy[nd]
    nx=x+dx[nd]
    return ny,nx,nd
ans=0
while True:
    ans+=1
    if ans >=1001:
        print(-1)
        break
    visited=[[0 for _ in range(N)] for _ in range(N)]
    for i in range(M):
        if shark[i] !=0:
            #flag = 상어 주위에 빈칸이 있는지 없는지 chk
            y,x,d,flag=shark[i][0],shark[i][1],shark[i][2],0
            for k in range(4):
                ny,nx,nd=set_direction(y,x,k)
                if is_valid_coord(ny,nx):
                    if board[ny][nx] ==0:
                        #빈칸이 있는 경우
                        flag=1
                        break
            # 상어 주위에 빈칸이 없는 경우 ,자신과 크기가 같은 곳으로 먼저 이동
            if not flag:
                for k in range(4):
                    ny,nx,nd=set_direction(y,x,k)
                    if is_valid_coord(ny,nx):
                        #자신과 크기가 같은곳을 찾으면 탈출
                        if board[ny][nx][0] == i+1:
                            break
            # 방문을 했는데,그곳에서 상어를 마주치는 경우
            # 상어는 동시에 움직이기 때문에, 이렇게 처리해야함!
            if visited[ny][nx]:
                if visited[ny][nx] < i+1:
                    shark[i]=0
                else:
                    shark[visited[ny][nx]-1] =0
            # 진짜 빈칸이면, 그냥 가면된다.
            else:
                visited[ny][nx] = i+1
                shark[i] =[ny,nx,nd]
    update_smell()
    update_shark()
    #1번 상어만 남았을 때
    if shark.count(0) ==M-1:
        print(ans)
        break