[백준] 16236 아기 상어, python

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

16236번: 아기 상어

import sys; input = sys.stdin.readline
from collections import deque
def search(start, size, board):
    d = [(-1, 0), (0, -1), (0, 1), (1, 0)]
    ret = []
    visit = [[-1 for _ in range(N)] for _ in range(N)]
    visit[start[0]][start[1]] = 0
    q = deque()
    q.append(start)
    while q:
        r, c = q.popleft()
        for i in range(4):
            dr = r + d[i][0]
            dc = c + d[i][1]
            if 0 <= dr < N and 0 <= dc < N:
                # 방문한곳이면 넘어감
                if visit[dr][dc] > -1: continue
                if board[dr][dc]: # 물고기인 경우
                    if board[dr][dc] < size:
                        visit[dr][dc] = visit[r][c] + 1
                        ret.append((dr,dc))
                    elif board[dr][dc] == size:
                        visit[dr][dc] = visit[r][c] + 1
                        q.append((dr, dc))
                else: # 빈 칸인 경우
                    visit[dr][dc] = visit[r][c] + 1
                    q.append((dr, dc))
        if ret: # 같은 거리인 경우 어떻게 확인?
            if q and visit[q[0][0]][q[0][1]] == visit[r][c]:
                continue
            break
    if ret:
        ret.sort(key=lambda x:(x[0], x[1]))
        return (ret[0][0], ret[0][1], visit[ret[0][0]][ret[0][1]])
    return False


N = int(input())
_map = []
pos = [-1, -1]
size, cnt = 2, 0
answer = 0
for i in range(N):
    tmp = list(map(int, input().split()))
    _map.append(tmp)
    for j in range(N):
        if tmp[j] == 9:
            pos[0], pos[1] = i, j

while True:
    exist = search(pos, size, _map)
    if not exist: break
    _map[pos[0]][pos[1]] = 0
    _map[exist[0]][exist[1]] = 9
    pos[0], pos[1] = exist[0], exist[1]
    answer += exist[2]
    cnt += 1
    if cnt == size:
        size += 1
        cnt = 0

print(answer)

 

BFS을 활용한 시뮬레이션을 구현하는 문제이다.

이 문제는 먹을수 있는 물고기를 탐색하는 것과 탐색후 이동 및 상태 갱신으로 나눌수 있다. 

첫번째는 탐색 부분이다.

탐색을 할때 BFS를 활용하여 모든 부분에 대해서 먹을수 있는 가장 가까운 물고기를 찾았다. 그리고 크기가 작은 물고기만 먹을수 있고, 크기가 같은 경우는 지나갈수만 있게 설정하였다. 같은 거리에 있는 경우 가장 위에 그리고 가장 왼쪽에 있는 순서대로 찾아야하므로 key를 사용하여 정렬한뒤 첫번째 위치 값과 움직인 거리를 리턴하였다. 먹을수 있는 물고기를 찾지 못한 경우는 False를 리턴하였다.

두번째는 이동 및 상태 갱신이다.

False를 리턴 받았을 경우 엄마 상어를 불러야하므로 반복문을 끝내게 하였다. 그 외 위치값과 거리를 리턴 받은 경우 기존 상어가 있는 위치를 갱신해주었고 움직인 거리도 더해주었다. 그리고 물고기를 상어의 크기만큼 먹으면 크기가 커지는 것을 구현하였다.

반복문 이후 마지막에 움직인 거리를 출력해서 정답을 받았다.

---

시뮬레이션이어서 실행시간이 오래 걸릴줄 알았는데 생각보다 오래 걸리지 않았다. 왜그런지는 잘 모르겠다.