BOJ 16236 아기상어 - Python

티어
골드 3

문제 링크
https://www.acmicpc.net/problem/16236

풀이
bfs를 통해 먹을 수 있는 물고기들을 구한다.
이때, 우선순위 : 거리 (dist), x 좌표(가장 위), y 좌표 (가장 왼쪽)

우선순위 별로 정렬된 물고기 하나를 먹고, 다시 bfs를 수행하면 된다.
이 때, queue가 비어있다면 먹을 물고기가 없는 것이므로 종료.


착오한 점
우선 순위에 따라 dx, dy를 설정해 놓으면 우선 순위 별로 찾아 질 것이라고 생각했다.

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

설정에 따라 (-1, 0), (0, -1), (0, 1), (1, 0) 순으로 방문하기 때문에, 우선순위도 맞을 것 같았지만 다음 상황에서 문제가 됐다.

# Shark.size = 3

5 4 Shark 0 2 4
4 2   0   3 4 5
3 2   9   5 6 6
2 1   2   3 4 5
3 2   1   6 5 4
6 6   6   6 6 6

우선 순위에 따르면, ( 0, 4 )인 물고기를 먹어야 하는데 ( 0, -1 )이 먼저 queue에 들어가므로, ( 1,1 )물고기를 먹게 된다.

따라서 해당 dx, dy 설정으로도 해결이 안되어, 먹을 수 있는 물고기들을 모두 넣고 정렬하는 방법으로 해결하였다.

코드 해설

Class - Index로 꺼내고 싶지 않아 이렇게 만들었다. 큰 의미는 없음

# 상어의 x, y 좌표, size와 먹은 횟수 ( eat )을 저장할 Class
class Shark:
    def __init__(self) -> None:
        self.x = 0
        self.y = 0
        self.size = 2
        self.eat = 0
        
# 물고기의 좌표와 거리를 저장할 Class
class Fish:
    def __init__(self, x, y, dist) -> None:
        self.x = x
        self.y = y
        self.dist = dist

사용자 Input 처리

N = int(get())
board = []
dx = [-1, 0, 0, 1]
dy = [0, -1, 1, 0]

shark = Shark()
que = deque()
answer = 0

for i in range(N):
    temp = list(map(int, get().split()))

    for j in range(N):
        if temp[j] == 9:
            shark.x, shark.y = i, j
            temp[j] = 0

    board.append(temp)

• 입력 중 9인 값이 상어이므로, shark를 초기화하고 다시 0으로 되돌린다.

bfs 부분

• 상어가 먹이를 먹고 난 후에는 아무 곳이든 다시 갈 수 있다.
  -> visited를 매번 다시 초기화

나머지 구현은 일반 bfs와 같고, 먹을 수 있다면 fish_list에 추가했다.
더이상 먹을 물고기가 없다면, fish_list를 우선순위에 맞게 정렬한 뒤
fish_list와 que를 clear시켜줬다.

while True:
    visited = [[False for _ in range(N)] for _ in range(N)]
    visited[shark.x][shark.y] = True

    fish_list = []

    que.append([shark.x, shark.y, 0])

    while que:
        que_x, que_y, que_dist = que.popleft()

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

            if x < 0 or x >= N or y < 0 or y >= N: continue
            
            if visited[x][y]: continue

            if board[x][y] > shark.size: continue

            visited[x][y] = True

            if board[x][y] == shark.size or board[x][y] == 0:
                que.append([x, y, que_dist+1])
            else:
                fish_list.append(Fish(x, y, que_dist + 1))
    
    if fish_list:
        fish_list.sort(key=lambda fish: [fish.dist, fish.x, fish.y])

        fish = fish_list[0]

        shark.x = fish.x
        shark.y = fish.y
        shark.eat += 1

        answer += fish.dist

        board[shark.x][shark.y] = 0

        if shark.size == shark.eat:
            shark.size += 1
            shark.eat = 0

        que.clear()
        fish_list.clear()

    else:
        break
        
print(answer)

전체 코드

import sys
from collections import deque

def get():
    return sys.stdin.readline().rstrip()

class Shark:
    def __init__(self) -> None:
        self.x = 0
        self.y = 0
        self.size = 2
        self.eat = 0

class Fish:
    def __init__(self, x, y, dist) -> None:
        self.x = x
        self.y = y
        self.dist = dist


N = int(get())
board = []
dx = [-1, 0, 0, 1]
dy = [0, -1, 1, 0]

shark = Shark()
que = deque()
answer = 0

for i in range(N):
    temp = list(map(int, get().split()))

    for j in range(N):
        if temp[j] == 9:
            shark.x, shark.y = i, j
            temp[j] = 0

    board.append(temp)

while True:
    visited = [[False for _ in range(N)] for _ in range(N)]
    visited[shark.x][shark.y] = True

    fish_list = []

    que.append([shark.x, shark.y, 0])

    while que:
        que_x, que_y, que_dist = que.popleft()

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

            if x < 0 or x >= N or y < 0 or y >= N: continue
            
            if visited[x][y]: continue

            if board[x][y] > shark.size: continue

            visited[x][y] = True

            if board[x][y] == shark.size or board[x][y] == 0:
                que.append([x, y, que_dist+1])
            else:
                fish_list.append(Fish(x, y, que_dist + 1))
    
    if fish_list:
        fish_list.sort(key=lambda fish: [fish.dist, fish.x, fish.y])

        fish = fish_list[0]

        shark.x = fish.x
        shark.y = fish.y
        shark.eat += 1

        answer += fish.dist

        board[shark.x][shark.y] = 0

        if shark.size == shark.eat:
            shark.size += 1
            shark.eat = 0

        que.clear()
        fish_list.clear()

    else:
        break
        
print(answer)