[백준] 19237번: 어른 상어 - 파이썬(python)

 

 

 

 

나의 풀이

import copy
import sys

input = sys.stdin.readline

n, m, k = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(n)]  # 격자판
smell = [[[0, 0] for _ in range(n)] for _ in range(n)]

shark_dir = [0] + list(map(int, input().split()))  # 현재 상어 방향

dir_rank = [[]]  # 상어의 방향별 우선순위
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

for i in range(m):
  array = []
  for j in range(4):
    array.append(list(map(int, input().split())))
  dir_rank.append(array)


def move(arr):  # 상어 움직이기
  global dead
  a = copy.deepcopy(arr)  # 상어들이 이동한 후의 배열
  for x in range(n):
    for y in range(n):
      if arr[x][y] > 0:  # 상어가 위치한 곳이라면
        shark_num = arr[x][y]  # 상어 번호
        d = shark_dir[shark_num]  # 상어의 현재 방향

        tmp = False
        for p in range(4):
          nd = dir_rank[shark_num][d - 1][p]  # p번째 우선순위 방향
          nx = x + dx[nd - 1]  # p번째 우선순위로 이동했을 때 x
          ny = y + dy[nd - 1]  # p번째 우선순위로 이동했을 때 y
          if 0 <= nx < n and 0 <= ny < n:
            if smell[nx][ny][0] == 0:  # 냄새가 없는 칸이라면
              if a[nx][ny] == 0:  # 다른 상어가 없다면
                a[nx][ny] = arr[x][y]
                a[x][y] = 0
              else:  # 다른 상어가 있다면
                if a[nx][ny] > a[x][y]:
                  a[nx][ny] = arr[x][y]  # 해당 칸의 상어 내쫓기
                dead += 1
                a[x][y] = 0
              shark_dir[shark_num] = nd  # 방향 갱신
              tmp = True
              break

        if not tmp:
          # 모든 인접한 칸에 냄새가 존재한다면
          for p in range(4):
            nd = dir_rank[shark_num][d - 1][p]
            nx = x + dx[nd - 1]
            ny = y + dy[nd - 1]
            if not (0 <= nx < n and 0 <= ny < n):
              continue
            if smell[nx][ny][0] == shark_num:  # 내 냄새가 있는 칸으로 이동
              a[nx][ny] = arr[x][y]
              a[x][y] = 0
              shark_dir[shark_num] = nd
              break
  return a


def update_smell(k):  # 냄새 정보 업데이트
  for i in range(n):
    for j in range(n):
      if smell[i][j][1] == 1:  # 0초가 됐으므로 냄새 없애기
        smell[i][j][0], smell[i][j][1] = 0, 0
      else:
        smell[i][j][1] -= 1  # 남은 시간 -1
      if arr[i][j] != 0:
        # 상어번호, k초가 남음
        smell[i][j][0], smell[i][j][1] = arr[i][j], k


time = 0  # 시간
dead = 0  # 퇴출된 상어 수
while True:
  if time >= 1000:
    time = -1
    break
  update_smell(k)
  arr = copy.deepcopy(move(arr))

  time += 1
  if dead == m - 1:  # 남은 상어가 한 마리라면
    break

print(time)

상어 가족아 두번다시 만나지말자....

구현문제 너무 힘들다ㅠㅠ

긴 템포로 풀어야 한다는 것이 가장 힘든 것 같다...

 

 

문제풀이의 큰 순서는 다음과 같다.

 

1. 정보 저장

• arr 은 상어 혹은 빈칸이 존재하는 문제 풀이의 배경이다.
• smell 은 [i][j] 에 냄새가 존재하는지의 여부를 저장하는 변수이다.
• shark_dir 은 i 번호의 상어의 현재 방향을 가리킨다.
• dir_rank 는 i번호상어의 방향별(1,2,3,4) 우선순위를 저장하고 있다.

2. 냄새 업데이트 [상어번호, 남은시간] 

• 시간은 k초로 초기화되고, 1초가 지날 때마다 -1이되며, 0이되는 순간 smell[i][j] = [0,0] 으로 냄새가 사라진다.

3. 상어 이동 

• arr(격자판) 에 존재하는 모든 상어들이 이동을 시작한다.
• 현재 상어 방향의 우선순위에 따라 1~4순위 방향으로 인접한 칸을 탐색해본다.
  • 인접한 칸에 아무런 냄새도 존재하지 않는다면,
    • 다른 상어가 존재한다면, 더 작은 상어만 남기고 큰 번호의 상어는 죽는다. -> dead += 1
    • 빈칸이라면, 해당칸으로 이동한다
  • 냄새가 존재하지 않는 칸으로 이동했다면 다음 상어를 탐색한다.
  • 만약, 모든 인접한 칸에 냄새가 존재한다면 현재 방향의 우선순위에 따라 탐색하면서
  • 내 냄새가 있는 칸을 찾으면 바로 이동한다.

4. 1초 증가

• 만약 죽은 상어가 m-1 이라면, 남아있는 상어가 한 마리이므로 반복문을 종료한다.