[백준 - Python] 16236 - 아기 상어

0. 문제 링크

 

 

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

16236번: 아기 상어

---

1. 풀이 방법

 

 

일단 해당 문제에서 가장 싫은 조건이 가장 위, 그런 것이 여러 마리라면 가장 왼쪽 이라는 조건이다.

먹이를 찾는다고 해서 끝이 아니라, 먹을 수 있는 먹이를 찾은 후에 거기서 조건을 통해 찾아야 하는 것 !

아무튼 이 문제는 BFS를 상하좌우, 상좌우하 뭐 이렇게 한다고 해서 풀리지 않는다. ㅜㅜ

 

우선 먹이를 먹는 순간 방문 표시는 리셋 해야 하므로 원본 맵의 복사본을 만들어놓는다.

방문 표시는 원본 맵을 변경하는 식으로 표시를 했다.

아무튼 먹을 수 있는 모든 먹이를 찾고, 거기서 찾는 것은 비효율적일 것 같다는 것이 나의 생각이었다.

따라서 upper 변수를 도입하여, 먹이를 찾는 순간, 상어와 먹이까지의 거리가 최대 허용 거리가 되고, 이를 upper 변수에 넣었다.

만약 맨 처음 찾은 먹이와의 거리가 2인데, 3이나 걸리는 거리에 있는 먹이를 먹을 필요가 없다는 뜻

따라서 upper 보다 큰 거리로 탐색을 한다면, 그대로 끝내고 can_eat 배열에서 정렬을 하여 먹이를 먹었다.

최종적으로 원본 맵의 복사본을 다시 복사함으로써 문제를 풀 수 있었다.

---

2. 코드

 

 

from collections import deque
from copy import deepcopy

n = int(input())
board = [[b for b in map(int, input().split())] for _ in range(n)]
for i in range(n):
    try:
        check = [i, board[i].index(9)]
    except:
        continue

board[check[0]][check[1]] = 0       # 상어의 위치를 0으로 둠
board_ori = deepcopy(board)     # 원본 저장

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

flag, upper, size, exp, cnt = False, 999, 2, 0, 0        # 찾았다는 표시     # 먹을 수 있는 물고기까지의 최대 거리
can_eat = []        # 먹을 수 있는 물고기의 좌표
dq = deque()
dq.append([check[0], check[1], 0])

while dq:
    y, x, dist = dq.popleft()
    if dist + 1 <= upper:       # 허용 가능 거리보다 작거나 같을 때
        for i in range(4):
            ny, nx = y + dy[i], x + dx[i]
            if 0 <= ny < n and 0 <= nx < n:
                if board[ny][nx] > size:
                    continue
                if board[ny][nx] == 0 or board[ny][nx] == size:     # 그냥 통과만 가능
                    dq.append([ny, nx, dist + 1])
                    board[ny][nx] = 999     # 방문 표시
                elif board[ny][nx] < size:      # 먹을 수 있음
                    if not flag:        # 아직 먹을 수 있는 애가 없음
                        flag, upper = True, dist + 1     # 먹을 수 있는것을 찾음, 허용 가능 최대 거리가 됨
                    can_eat.append([ny, nx, dist + 1])        # 먹을 수 있는 물고기의 좌표를 저장, 이 물고기를 넘어서는 좌표는 탐색할 필요가 없음
                    board[ny][nx] = 999     # 방문 표시
                    
    if flag and (dist + 1 > upper or len(dq) < 1):      
    # 먹을 수 있는 물고기가 있어야 하고,
    # 허용 가능 거리를 모두 탐색했거나, 허용 가능 거리와 같음에도 방문할 곳이 없을 때
        can_eat.sort(key = lambda x : (x[0], x[1]))     # 기준에 맞게 정렬함
        y, x, dist = can_eat.pop(0)     # 가장 우선 순위에 있는 먹잇감
        dq.clear(), can_eat.clear()     # 모든 dq를 초기화 함
        dq.append([y, x, dist])     # 가장 우선 순위에 있는 먹잇감 위치부터 다시 시작함
        board_ori[y][x] = 0
        board = deepcopy(board_ori)     # board 복구
        flag, upper = False, 9999
        cnt = dist

        exp += 1
        if exp == size:     # 경험치를 채운다면
            exp = 0
            size += 1
print(cnt)

---

3. 마무리

 

 

꽤 어려웠던 문제였다.