???

1. 문제

16236번: 아기 상어

2. 개요

N * N 보드에 상어와 물고기가 있다. 상어는 자기보다 큰 물고기가 있는 칸으로 이동이 불가하다. 작은 물고기라면 먹을 수 있다. 아기 상어의 크기는 2이고 자신의 크기만큼의 물고기를 먹는다면 크기가 1씩 증가한다.

이동 규칙은 다음과 같다.

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

위와 같은 조건에서 물고기를 먹을 수 없을 때 까지의 이동 거리를 구하는 그래프 탐색 문제.

3. 코드 및 추가내용

처음 코드를 작성할 때는

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

해당 조건을 단순히 현재 위치에서 $\uparrow$ , $\leftarrow$, $\rightarrow$, $\downarrow$ 순서대로 비교해서 먹이를 찾아낼 수 있을 거라고 생각했는데, 이게 잘못된 생각이었다.

// 9 - 상어, F - 먹이
0 9 0 F
F 0 0 0
0 0 0 0
0 0 0 0

인 경우 규칙대로라면 0행 4열의 먹이를 먹어야하지만, 작성한 코드에서는 대각선 아래의 먹이쪽으로 이동하는 오류가 있었다.

import sys
from collections import deque

N = int(sys.stdin.readline())

board = []
feed = []
_visited = [[0 for i in range(N)] for j in range(N)]
q = deque()
for i in range(N):
    board.append(list(map(int, sys.stdin.readline().split())))
    for j in range(N):
        if board[-1][j] == 9:
            board[i][j] = 0
            start = [i, j]

bs_size = 2
ate = -1
feed.append(start)
dirY, dirX = [-1, 0, 0, 1], [0, -1, 1, 0]
ans = 0

visited = [[v[i] for i in v] for v in _visited]
visited[start[0]][start[1]] = 1

while feed:
    feed.sort(key= lambda x : (x[0], x[1]))
    q.clear()
    q.append(feed[0])
    feed.clear()

    ate += 1
    if ate >= bs_size:
        bs_size += 1
        ate = 0
    
    ans += visited[q[0][0]][q[0][1]] - 1
    board[q[0][0]][q[0][1]] = 0
    visited = [[0 for _ in v] for v in _visited]
    visited[q[0][0]][q[0][1]] = 1

    tmp = deque()
    while q:
        now = q.popleft()
        nowY, nowX = now[0], now[1]

        for i in range(4):
            nextY, nextX = nowY + dirY[i], nowX + dirX[i]

            if nextY < 0 or nextY >= N or nextX < 0 or nextX >= N:
                continue
            if board[nextY][nextX] > bs_size:
                continue
            if visited[nextY][nextX]:
                continue

            if board[nextY][nextX] == bs_size:
                pass

            elif 0 < board[nextY][nextX] < bs_size:
                feed.append([nextY, nextX])

            visited[nextY][nextX] = visited[nowY][nowX] + 1
            tmp.append([nextY, nextX])

        if not q and not feed:
            q = tmp
            tmp = deque()

print(ans)

BFS를 행할 때, 같은 깊이의 위치를 모두 확인한 후, 먹이에 해당하는 칸이 있다면 이를 정렬하여 y, x순으로 오름차순 정렬한 첫 값을 목표지점으로 정하고 이동시키는 방법으로 구현하여 해결했다.

Comments

You May Also Enjoy