백준 16236: 아기상어 (Python)

BOJ 16236 아기상어

💡 이전에 시도했다가 포기했던 문제이다. 기본적인 그래프 이론이 들어가고 거기서 추가적으로 조건을 설정해주어야 하는데

• 거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기, 그러한 물고기가 여러마리라면, 가장 왼쪽에 있는 물고기를 먹는다.

이 조건 때문에 말도 안되게 생각을 많이 하게 되었다.
결국 이 부분을 서칭으로 풀었는데 서칭을 해도 맘처럼 되진 않았다.
람다를 사용해서 풀이하는 방법도 있었는데 연습해도 나중에 람다로 풀이를 스스로 할 것 같지는 않아서 참고하지 않았다.

정답 코드

from collections import deque

def bfs():
  queue = deque([(now_i, now_j)])
  distance = [[-1] * n for _ in range(n)]
  distance[now_i][now_j] = 0
  
  while queue:
    x, y = queue.popleft()
        
    for i in range(4):
      nx = dx[i] + x
      ny = dy[i] + y
      
      if 0 <= nx < n and 0 <= ny < n:
        if shark_size >= graph[nx][ny] and distance[nx][ny] == -1:
          distance[nx][ny] = distance[x][y] + 1
          queue.append((nx, ny))

  return distance

def bite(distance):
    min_distance = 1e9
    min_x, min_y = 0, 0
    
    for i in range(n):
      for j in range(n):
        if distance[i][j] != -1 and 1 <= graph[i][j] < shark_size:
          if distance[i][j] < min_distance:
            min_x, min_y = i, j
            min_distance = distance[i][j]
        
    # 먹을 물고기가 없을 경우 min_distance 값이 변화 x            
    if min_distance == 1e9:
        return None
    else:
        return min_x, min_y, min_distance
      
n = int(input())
graph = [list(map(int, input().split())) for _ in range(n)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
now_i, now_j = 0, 0
shark_size = 2

# 현재 상어 좌표
for i in range(n):
  for j in range(n):
    if graph[i][j] == 9:
      now_i, now_j = i, j
      graph[i][j] = 0
      
time = 0
ate_fish = 0
while True:
  result = bite(bfs())
  if result is None:
    break
  else:
    x, y, distance = result
    now_i, now_j = x, y
    graph[now_i][now_j] = 0
    ate_fish += 1
    if ate_fish == shark_size:
      shark_size += 1
      ate_fish = 0
    time += distance

print(time)

풀이과정

문제 조건
종료 조건은 더이상 먹을 물고기가 없을 경우

그래프의 각 위치까지 아기상어 시작점로부터의 최단거리
1. 현재 상어 위치를 추출 후 너비우선탐색
2. 최단거리 탐색을 하면서 거리를 기록
3. 1초마다 1칸씩 움직일 수 있으므로 거리가 시간도 의미

먹을 수 있는 물고기 서칭
1. 최단거리 1e9로 설정, 최단거리를 재갱신해나가기 위함
2. 먹을 수 있는 물고기의 경우 해당 거리가 최단거리라면 재갱신
3. 해당 좌표로 아기 상어의 위치 값 또한 재갱신
4. 그렇게 계속해서 반복 진행

종료 조건
1. 최단거리를 1e9로 설정했는데 1e9가 들어오면 먹을 수 있는 물고기가 없다는 것으로 종료
2. 그외 None을 반환하지 않을 경우 구조분해할당을 통해 상어의 위치 재설정, 물고기를 먹은 경우에 대한 모든 처리

풀이 후기

아직 내 레벨에서는 혼자 풀기엔 많이 힘들었다.
위에서 말한 최단거리에 대한 조건 때문에 구현하기에 너무 벅찼다..

처음 visited로 방문을 체크하고 False 값으로 했는데 풀이를 진행하면서 최단거리를 나타내야겠고 해당 위치로부터의 값을 알았어야했다.
그러고보니 방문에 대한 조건은 애초에 필요하지 않았고 위치에 대한 카운팅 값만 필요하여서 쳐냈다.

먹을 수 있는 물고기를 서칭하는 부분에서 시간을 너무 많이 사용했다.
생각도 잘 떠오르지않았고, 조건을 세우는 것도 나에겐 너무 어려웠다.