[백준] 16236번 아기 상어

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

16236번: 아기 상어

 

 

아기 상어가 어디로 이동할지 결정하는 방법은 아래와 같다.

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

아기 상어의 이동은 1초 걸리고, 물고기를 먹는데 걸리는 시간은 없다고 가정한다. 즉, 아기 상어가 먹을 수 있는 물고기가 있는 칸으로 이동했다면, 이동과 동시에 물고기를 먹는다. 물고기를 먹으면, 그 칸은 빈 칸이 된다.

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

 

풀이

# 초기값 설정
for y in range(N):
    for x in range(N):
        if board[y][x] == 9:
            shark_y, shark_x = y, x
            board[y][x] = 0

shark_size = 2
answer = 0
eat = 0

처음 상어의 위치를 저장한 뒤 해당 배열의 값을 0으로 수정하고 상어의 크기는 2로 초기화했다.

 

이제 상어가 먹을 수 있는 물고기가 있다면 Y좌표, X좌표가 가장 작은 곳으로 이동해서 먹은 뒤 다시 탐색하면 된다.

총 3개의 while문을 이용하여 구현하였는데

• 탐색을 시작할 상어의 위치를 설정하고 방문 확인, 먹을 수 있는 물고기의 위치를 초기화한다.
  하위 반복 후, 먹을 수 있는 물고기가 있다면 이동하여 eat 횟수를 1 증가시킨다.
• 큐 사이즈만큼 반복을 하는 것으로 1번에 1칸씩 이동하게 한다.
• 실제로 4방향으로 이동하면서 먹을 수 있는 물고기인지 판단한다.

 

while True:
    dq = deque()
    dq.append((shark_y, shark_x, 0))
    visited = [[False for _ in range(N)] for _ in range(N)]
    visited[shark_y][shark_x] = True
    can_eat = []
    eat_flag = False

1번째 while문이다. 
이동할 좌표를 담을 deque와 방문 체크를 하는 visited, 먹을 수 있는 물고기의 좌표인 can_eat을 초기화한다.
eat_flag는 먹을 수 있는 물고기가 있는 경우 while을 빠져나오기 위해 설정하였다.

 

while dq:
    dq_size = len(dq)

				#### while ####
				#### ##### ####

if eat_flag:
	break

하위 while에서 나온만큼만 반복을 시켜 while당 1칸씩 이동하게 설정하였다.

 

        while dq_size:
            now_y, now_x, count = dq.popleft()
            dq_size -= 1

            for i in range(4):
                next_y, next_x = now_y + direction[i][0], now_x + direction[i][1]

                # 배열의 범위 밖이면 conitnue
                if next_x < 0 or next_x >= N or next_y < 0 or next_y >= N:
                    continue
                # 이미 방문했거나 상어보다 크기가 크면 continue
                if visited[next_y][next_x] or board[next_y][next_x] > shark_size:
                    continue

                if board[next_y][next_x] < shark_size and board[next_y][next_x] != 0:
                    can_eat.append((next_y, next_x, count + 1))
                    eat_flag = True
                visited[next_y][next_x] = True
                dq.append((next_y, next_x, count + 1))

좌표가 범위 밖에 있거나, 이미 방문 했거나 물고기가 상어보다 크기가 더 크면 넘어간다.
그게 아닌 경우에는 물고기가 없거나 동일한 경우에는 이동을 위해 dq에 넣고
물고기의 크기가 더 작은 경우 먹을 수 있는  can_eat에 넣는다.

deque에는 이동한 횟수인 count를 같이 넣는 것으로 나중에 물고기를 먹을 때, 몇 칸 이동하는지 알 수 있게 했다.

 

    if len(can_eat) > 0:
        # 0번에 가장 위쪽, 가장 왼쪽
        # 00 - y좌표, 01 - x좌표, 02 - 이동 횟수
        can_eat.sort()
        answer += can_eat[0][2]
        board[can_eat[0][0]][can_eat[0][1]] = 0
        eat += 1
        if eat == shark_size:
            shark_size += 1
            eat = 0
        shark_y, shark_x = can_eat[0][0], can_eat[0][1]
    else:
        break

먹을 수 있는 물고기가 있는 경우에는 정렬하여 Y, X좌표가 가장 작은 곳에 있는 물고기를 먹고
먹은 숫자를 1 증가시켰다. 먹은 숫자가 상어의 크기와 동일한 경우에는 상어의 크기를 1 증가시킨다.
마지막으로 상어의 좌표를 먹은 물고기의 좌표로 변경하면 된다.

 

 

전체 코드

from collections import deque

N = int(input())
board = [list(map(int, input().split())) for _ in range(N)]
direction = [[0, 1], [0, -1], [1, 0], [-1, 0]]


# 초기값 설정
for y in range(N):
    for x in range(N):
        if board[y][x] == 9:
            shark_y, shark_x = y, x
            board[y][x] = 0

shark_size = 2
answer = 0
eat = 0


while True:
    dq = deque()
    dq.append((shark_y, shark_x, 0))
    visited = [[False for _ in range(N)] for _ in range(N)]
    visited[shark_y][shark_x] = True
    can_eat = []
    eat_flag = False

    while dq:
        dq_size = len(dq)

        while dq_size:
            now_y, now_x, count = dq.popleft()
            dq_size -= 1

            for i in range(4):
                next_y, next_x = now_y + direction[i][0], now_x + direction[i][1]

                # 배열의 범위 밖이면 conitnue
                if next_x < 0 or next_x >= N or next_y < 0 or next_y >= N:
                    continue
                # 이미 방문했거나 상어보다 크기가 크면 continue
                if visited[next_y][next_x] or board[next_y][next_x] > shark_size:
                    continue

                if board[next_y][next_x] < shark_size and board[next_y][next_x] != 0:
                    can_eat.append((next_y, next_x, count + 1))
                    eat_flag = True
                visited[next_y][next_x] = True
                dq.append((next_y, next_x, count + 1))

        if eat_flag:
            break
        # 먹을 수 있는 물고기가 있으면
    if len(can_eat) > 0:
        # 0번에 가장 위쪽, 가장 왼쪽
        # 00 - y좌표, 01 - x좌표, 02 - 이동 횟수
        can_eat.sort()
        answer += can_eat[0][2]
        board[can_eat[0][0]][can_eat[0][1]] = 0
        eat += 1
        if eat == shark_size:
            shark_size += 1
            eat = 0
        shark_y, shark_x = can_eat[0][0], can_eat[0][1]
    else:
        break


print(answer)

단순히 BFS를 이용하여 탐색하는 것이 아니라 특정 조건에 따라서 탐색하는 좌표를 이동해야하기 때문에
조금 복잡했던 것 같다. 하지만 비슷한 문제의 종류가 많기 때문에 연습해야하는 유형이다.