[백준] 16236번: 아기 상어 (골드3, 파이썬)

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

16236번: 아기 상어

 

아이디어

bfs를 사용해서 풀었다.

1. maps 전체를 돌면서 먹을 수 있는 물고기가 있는지 확인
   1. 있다면(maps[i][j] < shark_size), fishes 리스트에 위치 추가
   2. 물고기가 하나도 없다면, 엄마 상어 부르기(break)
2. 상어의 위치부터 각 물고기한테 가는 최단거리 구하기
   1. 만약 최단거리가 같은 값이 있다면, 먼저 구한 값을 사용(문제 조건: 같은 거리에 있는 물고기에 대한 우선순위 확인)
3. 거리가 가장 가까운 물고기를 먹기
   1. 아기 상어가 물고기 위치로 이동 (아기 상어가 있던 위치는 0, 물고기의 위치는 9로 maps 업데이트)
   2. 현재 아기상어가 먹은 물고기의 양 하나 증가 (fish_count += 1)
   3. 만약 물고기의 양 == 현재 상어의 크기 라면
      1. fish_count = 0
      2. shark_size += 1
   4. 시간 계산 (move_count += 구한 최단거리)

 

findFishes: 먹을 수 있는 물고기의 위치 찾기

def findFishes(shark_size):
    global N
    fishes = []
    x, y = -1, -1
    for i in range(N):
        for j in range(N):
            if maps[i][j] == 9:
                x = i
                y = j

            elif maps[i][j] < shark_size and maps[i][j] != 0:
                fishes.append((i, j))
    return fishes, x, y

 

먹을 수 있는 물고기의 좌표가 저장된 리스트와 현재 상어의 위치를 반환해준다.

 

bfs: 상어의 위치에서 Fishes에 있는 좌표까지의 최단 거리 구하기

def bfs(now_x, now_y, pos_x, pos_y):
    global N
    global shark_size
    queue = deque()
    queue.append((now_x, now_y, 0))

    visited = [[0 for _ in range(N)] for _ in range(N)]
    visited[now_x][now_y] = 1

    min_distance = 1e9
    
    while queue:
        
        x, y, m = queue.popleft()

        if x == pos_x and y == pos_y:
            min_distance = min(min_distance, m)

        for d in dv:
            nx = x + d[0]
            ny = y + d[1]

            if nx < 0 or nx >= N or ny < 0 or ny >= N or maps[nx][ny] > shark_size or visited[nx][ny] == 1:
                continue
            elif maps[nx][ny] <= shark_size:
                visited[nx][ny] = 1
                queue.append((nx, ny, m+1))
                
    return min_distance

현재 상어의 위치부터 상하좌우로 이동하며 목표 좌표까지 가는 최단거리를 찾았다.

 

 

 

거리가 가장 가까운 물고기를 먹고 이동하기

fish_count = 0
move_count = 0
shark_size = 2
while True:
    fishes, shark_x, shark_y = findFishes(shark_size)

    if len(fishes) == 0:    # 먹을 수 있는 물고기가 없으면
        break

    else:
        distance = 1e9
        fish_x, fish_y = -1, -1          

        for i, j in fishes: 
            tmp_distance = bfs(shark_x, shark_y, i, j, N, shark_size)

            if tmp_distance < distance:
                fish_x = i
                fish_y = j
                distance = tmp_distance
        
        if distance == 1e9: # 갈 수 있는 곳이 없으면
            break

        maps[shark_x][shark_y] = 0
        maps[fish_x][fish_y] = 9

        shark_x = fish_x
        shark_y = fish_y
        
        fish_count += 1
        if fish_count == shark_size:
            shark_size += 1
            fish_count = 0

        move_count += distance

문제 요구사항에 맞게 단순히 구현하였다.

 

전체 코드

# 3:26 ~ 5:20 (1'54")
# python3 - 시간 초과
# pypy3 - 맞았습니당

from collections import deque

def findFishes(shark_size):
    global N
    fishes = []
    x, y = -1, -1
    for i in range(N):
        for j in range(N):
            if maps[i][j] == 9:
                x = i
                y = j

            elif maps[i][j] < shark_size and maps[i][j] != 0:
                fishes.append((i, j))
    return fishes, x, y


def bfs(now_x, now_y, pos_x, pos_y):
    global N
    global shark_size
    queue = deque()
    queue.append((now_x, now_y, 0))

    visited = [[0 for _ in range(N)] for _ in range(N)]
    visited[now_x][now_y] = 1

    min_distance = 1e9
    
    while queue:
        
        x, y, m = queue.popleft()

        if x == pos_x and y == pos_y:
            min_distance = min(min_distance, m)

        for d in dv:
            nx = x + d[0]
            ny = y + d[1]

            if nx < 0 or nx >= N or ny < 0 or ny >= N or maps[nx][ny] > shark_size or visited[nx][ny] == 1:
                continue
            elif maps[nx][ny] <= shark_size:
                visited[nx][ny] = 1
                queue.append((nx, ny, m+1))
                
    return min_distance

N = int(input())
maps = [[int(x) for x in input().split()] for _ in range(N)]
dv = [(-1, 0), (0, -1), (1, 0), (0, 1)]


fish_count = 0
move_count = 0
shark_size = 2
while True:
    fishes, shark_x, shark_y = findFishes(shark_size)

    if len(fishes) == 0:    # 먹을 수 있는 물고기가 없으면
        break

    else:
        distance = 1e9
        fish_x, fish_y = -1, -1          

        for i, j in fishes: 
            tmp_distance = bfs(shark_x, shark_y, i, j)

            if tmp_distance < distance:
                fish_x = i
                fish_y = j
                distance = tmp_distance
        
        if distance == 1e9: # 갈 수 있는 곳이 없으면
            break

        maps[shark_x][shark_y] = 0
        maps[fish_x][fish_y] = 9

        shark_x = fish_x
        shark_y = fish_y
        
        fish_count += 1
        if fish_count == shark_size:
            shark_size += 1
            fish_count = 0

        move_count += distance

print(move_count)

 

후기

PyPy3는 통과가 되지만, Python3로는 시간 초과가 나서 다른 사람의 코드를 찾아보았다.

나는 물고기의 위치를 먼저 계산한 후 dfs를 사용해서 각 목표까지 가는 최단거리를 , 다른 사람들은 상어의 위치만 찾은 후 dfs로 각 위치까지 가는 거리를 업데이트 한 후, 거리값이 작고 물고기가 있는 위치로 이동시키는 방법을 사용하였다.

우선 거리값과 물고기 위치를 업데이트하고, 물고기를 찾으면 fishes 리스트에 (x, y, 거리)를 추가해준다. 그 후,

fishes.sort(key= lambda x : (x[2],x[0],x[1])) # 거리, x, y 오름차순으로 정렬
    return fishes

이렇게 정렬 해주면, fishes의 0번째로 이동만하면 된다.

 

또, 문제에는 물고기 갯수로 분기를 해두었는데, 나는 상어의 사이즈보다 작은 물고기가 있지만, 먹으러 가는 길이 막혔을 때를 생각하다보니 물고기가 한마리여도 갈 수 있는 여부를 검사하느라 분기점이 늘었다.