[python] 백준 16236번: 아기 상어(BFS)

#  16236 아기 상어

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

16236번: 아기 상어

⭐ 코드

import sys
input = sys.stdin.readline

from collections import deque
N = int(input())
graph = [list(map(int, input().split())) for _ in range(N)]

baby_shark = []

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

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

shark_size = 2
for i in range(N):
    for j in range(N):
        if graph[i][j] == 9:
            baby_shark.append((i,j))

#  아기 상어 위치
x, y = baby_shark.pop()

def bfs(i,j, shark_size):
    distance = [[0] * N for _ in range(N)]
    visited = [[0] * N for _ in range(N)]
    # 아기 상어가 있는 칸에서 물고기가 있는 칸으로 이동할 때, 지나야하는 칸의 개수의 최솟값
    queue = deque()
    queue.append((i,j))

    visited[i][j] = 1
    temp = []

    while queue:
        xx, yy = queue.popleft()
        for i in range(4):
            nx = dx[i] + xx
            ny = dy[i] + yy

            if 0 <= nx < N and 0 <= ny < N and visited[nx][ny] == 0:

                if graph[nx][ny] <= shark_size:
                    queue.append((nx,ny))
                    visited[nx][ny] = 1 # 방문처리
                    distance[nx][ny] = distance[xx][yy] + 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,shark_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 == shark_size:
        shark_size += 1
        cnt = 0

print(result)

📝 풀이

문제를 읽자마자 주어진 조건과 고려해야 할 사항들이 너무 많아 까다롭다고 느꼈다. 문제에서 제시한 아기 상어의 조건은 다음과 같다.

 

1. 작은 물고기만 먹을 수 있음

2. 같은 사이즈의 물고기는 지나갈수만 있음

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

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

4. 자신의 크기아 같은 수의 물고기를 먹을 때 마다 크기가 1 증가한다.

5. 상어크키가 2면 2마리를 먹어야한다.

 

가까운 먹이를 찾는 문제이기 때문에 BFS를 생각해볼 수 있다. 현재 아기 상어의 위치를 기준으로 탐색을 시작해준다. bfs출력으로는 후보 리스트를 반환한다.

 

후보 리스트가 필요한 이유로는 가장 가까운 거리에 있는 먹이가 여러개 일 수 있기 때문이다. 후보 리스트는 정렬을 통해 우선 순위를 결정해준다. 후보 리스트의 후보 먹이 위치를 뽑아 그 위치로 이동한다.

맨 앞의 후보만 먹고 위치 이동 후 다시 BFS를 실행시켜주는데, 먹이 위치로 이동했을때 새로운 먹이 후보군의 우선순위가 달라질 수 있기 때문이다. 최종적으로 몇 개를 먹었고, 몇 초간 이동했는지 체크해준다.

🔓 정답 코드 뜯어보기

import sys
input = sys.stdin.readline

from collections import deque
N = int(input())
graph = [list(map(int, input().split())) for _ in range(N)]

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

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

baby_shark = [] # 1번
for i in range(N):
    for j in range(N):
        if graph[i][j] == 9:
            baby_shark.append((i,j))

#  아기 상어 위치
x, y = baby_shark.pop() # 2번

# 1번

먼저 아기 상어의 위치를 찾기위해 리스트를 생성해주고 이중 반복문을 통해 좌표 값을 저장시켜준다.

 

# 2번

저장한 좌표를 x, y에 할당시켜준다.

def bfs(i,j, shark_size):
    distance = [[0] * N for _ in range(N)] # 1번
    visited = [[0] * N for _ in range(N)]
    # 아기 상어가 있는 칸에서 물고기가 있는 칸으로 이동할 때, 지나야하는 칸의 개수의 최솟값
    queue = deque()
    queue.append((i,j))

    visited[i][j] = 1
    temp = [] # 2번

    while queue:
        xx, yy = queue.popleft()
        for i in range(4):
            nx = dx[i] + xx
            ny = dy[i] + yy

            if 0 <= nx < N and 0 <= ny < N and visited[nx][ny] == 0:

                if graph[nx][ny] <= shark_size: # 3번
                    queue.append((nx,ny))
                    visited[nx][ny] = 1 # 방문처리
                    distance[nx][ny] = distance[xx][yy] + 1 # 거리 증가
                    
                    if graph[nx][ny] < shark_size and graph[nx][ny] != 0: # 4번
                        temp.append((nx,ny, distance[nx][ny]))
    
    # 거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기, 그런 물고기가 여러마리라면, 가잔 왼쪽에 있는 물고기를 먹는다.
    return sorted(temp, key=lambda x: (-x[2], -x[0], -x[1])) # 5번

# 1번

거리를 체크해줄 distance 리스트와 방문 여부를 체크해줄 visited 리스트를 생성해준다. queue에 좌표값을 넣어주고 처음 좌표값을 방문처리해준다.

 

# 2번

문제에서 주어진 우선순위 조건을 탐색할 temp 리스트를 생성해준다. 그 이후 queue를 실행하면서 4방향 탐색을 진행해준다. 4방향을 탐색하면서 범위 내에 있고, 방문한 적이 없는 곳이라면 다음 로직을 실행시켜준다.

 

# 3번

탐색한 곳의 크기가 shark_size보다 작거나 같다면 지나갈 수 있는 곳이므로 해당 좌표를 queue에 넣어주고 방문처리 해준다. 추가적으로 이전값에 1 더한 값을 distance 리스트에 저장시켜준다.

 

# 4번

만약 탐색한 곳이 아기 상어보다 작으면서 상어라면 temp리스트에 좌표와 거리를 담아준다.

 

# 5번

최종적으로 temp에 조건 값들을 저장해주고 우선순위에 맞게 lambda를 통해 정렬시켜준다. 

cnt = 0
result = 0

while True:
    shark = bfs(x,y,shark_size) # 1번
    # 더 이상 먹을 수 있는 물고기가 공간에 없다면 브레이크
    if len(shark) == 0: # 2번
        break

    # 거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기, 그런 물고기가 여러마리라면, 가장 왼쪽에 있는 물고기를 먹는다.
    # 정렬한 결과를 반영    
    nx, ny, dist = shark.pop() # 3번

    # 움직이는 거리 합산
    result += dist # 4번
    graph[x][y] , graph[nx][ny] = 0,0

    # 상어좌표를 옮겨준다.
    x, y = nx, ny # 5번
    cnt += 1

    if cnt == shark_size: # 6번
        shark_size += 1
        cnt = 0

print(result)

# 1번

위에서 구한 아기 상어의 위치부터 bfs를 실행한다. bfs를 실행하고나서 먹었던 위치 값을 shark에 저장시켜준다.

 

# 2번

위치 값들이 shark에 저장되는데, 만약 저장된 shark가 없다면 먹이가 없다는 뜻이므로 break를 실행시켜준다.

 

# 3번

먹었던 상어의 위치와 소요된 거리를 nx, ny, dist에 저장시켜준다.

 

# 4번

움직였던 거리를 result에 계속해서 더해준다. 

 

# 5번

먹었던 위치로부터 다시 bfs를 실행해야 하므로 좌표를 옮겨준다.

 

# 6번

상어 크기와 cnt가 같다면 상어크기를 키워주고 지금까지 이동한 거리의 합계(result)를 출력해준다.