백준 16236 - 파이썬

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

16236번: 아기 상어

문제 풀이

이 문제는 조건들이 굉장히 까다로워서 처음에 이해하는데 시간이 좀 걸렸다. 요약해보면 다음과 같다.

 

1. 상어의 크기는 2이고, 자신보다 큰 물고기가 있는 칸은 지나갈 수 없다.

2. 상어는 자신보다 작은 물고기만 먹을 수 있다.

3. 크기가 같은 물고기는 먹을 수 없지만, 그 물고기가 있는 칸은 지나갈 수 있다.

4. 먹을 수 있는 물고기가 1마리면, 그 물고기를 먹으러 간다.

5. 먹을 수 있는 물고기가 1마리보다 많으면, 가장 가까운 물고기를 먹으러 간다.

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

7. 물고기를 먹으면 그 칸은 빈칸이 된다.(즉, 0이 됨)

8. 상어의 크기 = 먹은 물고기의 수(크기 상관 없음)

9. 물고기를 다 먹으면 종료

 

이처럼 조건이 매우 다양하기 때문에 구현시에 신경써야 할 부분도 많고, 생각할 부분도 많다. 조건이 너무 많은 나머지 생각을 제대로 정리하지 못해 다른 사람의 블로그를 찾아보았는데 정리하면 다음과 같다.

 

1. 상어의 크기, 물고기를 먹은 횟수를 저장하는 변수를 별도로 선언한다.

2. 물고기의 크기가 상어보다 크거나 같다면 먹지 못하므로 무시하고 지나간다.

3. 상어가 물고기를 먹기 전까지 움직일 때마다 이동거리를 1씩 증가시킨다.

4. 물고리를 먹은 횟수가 상어와 같다면, 상어 크기를 1 증가시키고 먹은 횟수를 초기화 한다.

5. 다음 물고리를 먹기 위해 이동할 때, 이미 갔던 곳을 다시 방문할 수 있다. 따라서 방문 체크 리스트도 모두 초기화 하고, 큐에 들어있는 좌표도 업데이트 시킨다.

6. 먹을 수 있는 물고기를 저장한 리스트의 길이가 0이라면 종료한다.

 

이 블로그에서는 구현시 놓치면 안되는 포인트를 짚어두었다.

 

1. 매 탐색마다 모든 물고기의 거리를 구하면 시간초과가 난다.

2. BFS 탐색이 최적의 경로를 탐색 한다는 점을 이용한다. 즉, 물고기를 한번이라도 만나면 그 길이 최단거리다.

 

코드

from collections import deque
import sys

input = sys.stdin.readline

n = int(input())

graph = [list(map(int, input().split())) for _ in range(n)]

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

cnt = 0
x, y, size = 0, 0, 2

for i in range(n):
  for j in range(n):
    if graph[i][j] == 9:
      x, y = i, j


def bfs(x, y, shark_size):
  q = deque()
  distance = [[0] * n for _ in range(n)]
  visited = [[0] * n for _ in range(n)]

  visited[x][y] = 1
  q.append((x, y))
  temp = []

  while q:
    x, y = q.popleft()

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

      if 0 <= nx < n and 0 <= ny < n and visited[nx][ny] == 0:
        if graph[nx][ny] <= shark_size:
          q.append((nx, ny))
          visited[nx][ny] = 1
          distance[nx][ny] = distance[x][y] + 1

          if graph[nx][ny] < shark_size and graph[nx][ny] != 0:
            temp.append((nx, ny, distance[nx][ny]))

  return sorted(temp, key=lambda x: (-x[2], -x[0], -x[1]))


cnt = 0
result = 0

while True:
  shark = bfs(x, y, size)

  if len(shark) == 0:
    break

  nx, ny, dist = shark.pop()

  result += dist
  graph[x][y], graph[nx][ny] = 0, 0
  x, y = nx, ny
  cnt += 1

  if cnt == size:
    size += 1
    cnt = 0

print(result)

# https://resilient-923.tistory.com/357 참고

예제 시물레이션

 

 

이번 문제를 풀 때 조건이 너무 많고 까다로워서 처음부터 겁을 낸거 같다. 구현은 주어진 조건을 차근차근 코드로 옮기면 되는 것을 알고 있음에도 말이다. 많은 조건에 겁을 낸것도 문제지만, 아직 주어진 조건을 코드로 구현하기 위해서 어떤 변수를 어떻게 선언하고, 함수를 구현할지도 제대로 못 정하는거 같다. 백준 문제를 정리할때마다 남기는 말이지만 역시 많이 풀어보고 생각하는 수 밖에 없는 거 같다.