[python] BOJ 백준 19237: 어른상어

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. 해결방법   

이 문제는 구현, 시뮬레이션 문제이다. 1초에 일어나는 사건을 상어가 냄새를 남기고, 상어가 이동하고, 상어의 냄새가 흐려지는 3단계로 나눌 수 있다. 제한시간 1000초동안 1번상어만 남을때까지 이 3단계를 반복해주면된다. 상어의 냄새를 저장하는 board배열, 상어의 좌표와 방향을 저장하는 shark배열, 각 상어별 우선순위를 저장하는 rank배열 3개를 이용하여 구현해주었다.  

1) smell 함수: 자신의 위치에 냄새를 남기는 함수이다. 상어 배열을 돌면서 아직 살아있는 상어에 대하여 상어가 있는 위치에 [k초, 상어번호]를 저장해준다. 문제에서 냄새가 몇초간 남는지는 k변수로 제공하며, 몇번 상어가 남겼는지를 저장해두어야 나중에 상어가 이동할때 자신의 냄새가 있는 좌표를 탐색할 수 있다. 

2) next 함수: 1초가 지나면 냄새가 옅어져야하므로 board배열을 돌면서 1이상인 값에 대해서 1씩 감소시켜주어야한다. 

3) move 함수: 상어가 갈수 있는 후보들을 탐색하여 이동하게 하는 함수이다. 상어가 겹치는 칸을 알아내기 위해서는 임시배열을 하나 생성해주어야한다. 상어 배열을 돌면서 상하좌우에 빈자리를 담는 배열과 자신의 냄새가 남아있는 배열을 각각 따로 구해주고, 만약 빈자리를 담는 배열이 비어있다면 최종 후보군은 자신의 냄새가 남아있는 배열로 지정해주어야한다. 최종후보군이 한자리라면 바로 방향과 좌표를 업데이트 해주면되지만, 만약 최종후보군이 여러개라면 우선순위와 비교하여 방향을 설정해주어야한다. 방향을 최종적으로 설정하고 임시배열에 추가를 해준다. 임시배열을 돌면서 만약 한칸에 여러마리의 상어가 들어있다면 번호가 낮은 상어만을 남겨두고 모두 지워준다. 

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,방향 
rank=[[] for _ in range(m)] #각 상어별 우선순위 


#위-아래-왼쪽-오른쪽
dx=[-1,1,0,0]
dy=[0,0,-1,1]

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

for i in range(n):
  for j in range(n):
    if board[i][j]!=0: #상어 번호: x좌표, y좌표, 방향
        shark[board[i][j]-1]=[i,j,d[board[i][j]-1]-1]
    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

#1초가 지나면 냄새가 1씩 줄어들기 
def next(board):
  for i in range(n):
    for j in range(n):
      if board[i][j][0]>0: #냄새가 남아있으면 
        board[i][j][0]-=1 #1씩 감소 
  return board

#상어 이동 
def move(shark):
  #임시배열 생성 (겹치는 상어를 제거하기위해)
  temp=[[[]for j in range(n)] for _ in range(n)]
  for i in range(len(shark)): #상어배열을 돌면서 
    if shark[i]: 
      x,y,d=shark[i] 
      candidate=[] #빈자리 
      my_candidate=[] #내냄새가 있는 곳 
      for k in range(4): #상하좌우 
        nx,ny=x+dx[k],y+dy[k]
        if 0<=nx<n and 0<=ny<n: #범위안에있으면 
          if board[nx][ny][0]==0: #빈자리라면 
            candidate.append((nx,ny,k))
          elif board[nx][ny][1]==i: #내냄새가 남아있는곳이라면
            my_candidate.append((nx,ny,k))
      new_d=d #상어의 다음방향 
      if not candidate: #빈자리가 없다면 
        candidate=my_candidate #최종후보군은 내냄새가 남아있는 곳 
      if len(candidate)>=2: #후보군이 여러개라면 
        shark_rank=rank[i][d] #우선순위대로 
        for r in shark_rank:
          flag=False
          for a,b,c in candidate: 
            if r-1==c: #우선순위와 일치하면 
              new_d=r-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] #상어 최종정보 업데이트
      temp[x+dx[new_d]][y+dy[new_d]].append(i) #임시배열에 저장 

    #임시배열을 돌면서  
    for i in range(n):
      for j in range(n):
        if len(temp[i][j])>1: #상어가 겹치는 칸이있으면 
            temp[i][j].sort() #정렬해서 맨앞 상어만 살리기 
            for k in temp[i][j][1:]:
                shark[k]=[] #나머지 상어는 삭제 

    cnt=0 #남은 상어의 개수 
    for i in range(m):
        if shark[i]!=[]:
            cnt+=1

  return shark,cnt

for i in range(1000):
  board=smell(board,shark) #냄새남기기
  shark,live=move(shark) #상어이동
  board=next(board) #1초 지남 
  if live==1: #1번상어만 남았으면 
    print(i+1) #탈출 
    break
else: #1000초가 지나버린경우 
  print(-1)

 

⭐️난이도:  골드 2 ⭐️

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

19237번: 어른 상어