[Python] 백준 아기상어

1. 문제 - 백준 아기상어 (삼성 SW 역량테스트 기출)

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

 

💡 문제 접근 방식

 

BFS + 시뮬레이션/구현 문제이다.

거리는 아기 상어가 있는 칸에서 물고기가 있는 칸으로 이동할 때, 지나야하는 칸의 개수의 최솟값

처음에 이부분을보고 "거리"는 아기 상어의 좌표와 물고기가 있는 좌표 거리의 절댓값을 구하면 되지 않나? 생각했지만

 

아기 상어는 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없고, 나머지 칸은 모두 지나갈 수 있다.
아기 상어는 자신의 크기보다 작은 물고기만 먹을 수 있다. 따라서, 크기가 같은 물고기는 먹을 수 없지만, 그 물고기가 있는 칸은 지나갈 수 있다.

- 지나갈 수 있는 조건을 명시해줬기에, 아 이 문제는 물고기가 더이상 남아있지 않을때까지 BFS로 탐색하면서 최단 거리를 구하여 거리가 짧은 순서대로 물거리를 먹는 문제구나 라고 접근했다.

- BFS는 최단 거리를 보장해주므로, 아기 상어의 위치가 바뀔 때마다 BFS를 통해 각 물고기들과의 최단 거리를 구한다.

 

✅ 풀이

from collections import deque

answer = 0
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

n = int(input())
board = []
x, y = 0, 0   # 아기상어의 위치
size = 2   # 가장 처음 아기 상어의 크기는 2이다.

for i in range(n):
  board.append(list(map(int, input().split())))
  for j in range(n):
    if board[i][j] == 9:   # 아기상어 위치 찾음
      x, y = i, j
      board[x][y] = 0

def bfs():    # 아기상어 위치가 바뀔때마다, 각 물고기까지 가기에 필요한 최소 칸의 갯수 = 최단 거리를 구할 BFS 함수
  q = deque([(x, y)])   # 처음엔 아기상어 위치부터 시작
  visited = [[0] * n for _ in range(n)]

  while q:
    nx, ny = q.popleft()

    for i in range(4):
      mx = nx + dx[i]
      my = ny + dy[i]

      if 0<=mx<n and 0<=my<n and not visited[mx][my] and board[mx][my] <= size:   # 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없다.
        visited[mx][my] = visited[nx][ny] + 1   # 최단거리 갱신
        q.append((mx, my))

  positions = []
  for i in range(n):
    for j in range(n):    # 먹을 수 있는 물고기들의 좌표와 최단거리를 구함
      if 0 < board[i][j] < size and visited[i][j]:
        positions.append((i, j, visited[i][j]))

  return positions

count = 0
while True:
  positions = bfs()
  
  if not positions:  # 먹을 수 있는 물고기가 없으므로 엄마 상어에게 도움을 요청한다 --> 멈춘다.
    break

  positions.sort(key=lambda x:(x[2], x[0], x[1]))  
  # 거리가 가장 가까운 물고기를 먹으러 가되, 여러개가 있다면 가장 위에 있는 물고기(x좌표 오름차순), 가장 왼쪽에 있는 물고기(y좌표 오름차순)에 있는 물고기를 먹으러간다.
  nx, ny, dist = positions[0]   # 해당하는 물고기의 좌표, 거리
  
  count += 1        # 물고기를 먹은 갯수 + 1
  board[nx][ny] = 0   # 물고기를 먹었으므로 0으로 갱신
  x, y = nx, ny       # 아기상어 위치 갱신
  answer += dist      # 아기상어는 1초마다 인접한 칸으로 1칸씩 이동하므로, 해당 거리가 곧 물고기까지 가는 데 걸리는 시간을 의미한다.

  # 아기 상어는 자신의 크기와 같은 수의 물고기를 먹을 때 마다 크기가 1 증가한다. 예를 들어, 크기가 2인 아기 상어는 물고기를 2마리 먹으면 크기가 3이 된다.
  if count == size:
    size += 1
    count = 0

print(answer)

 

- 아기상어의 변하는 위치마다 가장 가까운 거리의 물고기를 구하기 위해 BFS를 사용하되, 

- 먹을 수 있는 물고기가 1마리보다 많다면, 거리가 가장 가까운 물고기를 먹으러 간다.
 - 거리는 아기 상어가 있는 칸에서 물고기가 있는 칸으로 이동할 때, 지나야하는 칸의 개수의 최솟값이다.
- 거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기, 그러한 물고기가 여러마리라면, 가장 왼쪽에 있는 물고기를 먹는다.

이 조건에 따라 편리하게 정렬하기 위해 BFS가 다 끝나면 좌표, 거리를 담을 리스트를 반환하도록 했다.

  positions.sort(key=lambda x:(x[2], x[0], x[1]))

 

key로 지정한 위 기준에 따라 거리가 가장 가까운 순서, 가장 위에 있는 물고기(x좌표 오름차순), 가장 왼쪽에 있는 물고기(y좌표 오름차순)으로 정렬한다.