[백준16236번] 아기상어(파이썬)

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

16236번: 아기 상어

 

길찾기까지는 쉬운데

조건 붙은 것이 살짝 까다로워서

'맞왜틀'이 반복되는 문제입니다.

사실, 아기상어가 먹을 좌표를 구하는 건

생각보다 간단한 편입니다.

BFS DFS로 길찾기하면 그만이니까요.

문제는 '물고기가 상어보다 큰 건 못지나간다'

라는 부분입니다.

OK의 경우를 본다면

현재 4 물고기가 목적지 사이에 가로 막혀있으므로

돌아서 가면 이동이 6입니다.

그런데, 무턱대고

'먹을 물고기 좌표를 구했으니

바로 좌표 사이의 거리 빼주면

쉽게 풀리네'

라고 하는 순간

이동이 4로 반영이 되면서

물고기를 먹는 좌표는 구했으나

이동거리를 잘못 넣어줄 수 있습니다.

 

저 같은 경우에는 visited에

좌표를 옮겨가면서 숫자를 넣어줬습니다.

초기 상어위치는 0으로 넣어두고

가까운 거리는 계속 +1를 해두면서 이동했습니다.

 

# 백준 16236 아기상어
from collections import deque

N = int(input())

graph = []

bx = 0
by = 0
b_size = 2
upgrade = 0

for i in range(N):
    data = list(map(int, input().split()))
    graph.append(data)
    for j in range(N):
        if data[j] == 9:
            bx = i
            by = j

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

graph[bx][by] = 0

time = 0

while True:
    # 상어가 먹을 수 있는 걸 BFS로 구해보자
    # move는 움직은 큐
    # eat은 먹을 수 있는 거 모아둔 큐
    # visited로 한번 탐색한 거 굳이 더 안가게 한다.
    shark_move = deque()
    shark_move.append([bx, by])

    shark_eat = []

    visited = [[-1] * N for _ in range(N)]
    # 실제적인 거리를 구하기 위해, visited 리스트에 최소 이동거리를 넣는다.
    visited[bx][by] = 0
    min_direct = 100000
    while shark_move:
        x, y = shark_move.popleft()

        for d in range(4):
            nx = x + dx[d]
            ny = y + dy[d]

            if nx < 0 or nx >= N or ny < 0 or ny >= N:
                continue
            # 빈칸이거나 아기상어보다 같거나 작은 경우만 지나갈 수 있다.
            if visited[nx][ny] == -1 and 0 <= graph[nx][ny] <= b_size:
                visited[nx][ny] = visited[x][y] + 1
                shark_move.append([nx, ny])

                if 0 < graph[nx][ny] < b_size:
                    # 최소거리를 구해야함
                    now_direct = visited[nx][ny]
                    if now_direct < min_direct:
                        shark_eat.clear()
                        min_direct = now_direct
                        shark_eat.append([nx, ny])
                    elif now_direct == min_direct:
                        shark_eat.append([nx, ny])

    # print(shark_eat)
    if not shark_eat:
        break

    shark_eat.sort()
    eat_x, eat_y = shark_eat.pop(0)
    # 왕 주의!!!!!!! 좌표 차이를 받는 게 아니라, 해당지점까지가는 최소 거리다!!
    time += visited[eat_x][eat_y]
    bx, by = eat_x, eat_y
    graph[bx][by] = 0

    upgrade += 1
    if upgrade == b_size:
        b_size += 1
        upgrade = 0
    # print(bx,by)
    # print(b_size)
    # print(graph)
    # print(time)
    # print()

print(time)

 

https://yunanp.tistory.com/12

[BFS, 구현] 백준 16236 아기 상어 python

https://11001.tistory.com/96

파이썬(python) 백준 16236 : 아기 상어

https://resilient-923.tistory.com/357

[백준] 16236(파이썬) - 아기 상어

 

이 문제는 

'문제에서 요구하는 최소거리'

라는 관점에서 정리하기 좋은 문제입니다.

흔히, '최소거리'라고 하면

'좌표평면상의 거리'라고 생각하기 쉽습니다.

하지만 길찾기 케이스를 생각한다면

중간에 벽을 만나는 케이스가 있어

그런 것을 반영해야합니다.

정말 내가 구하는 게 문제에서 구하는 최소거리가 맞는지

한번 고민하게 만들어주는 문제입니다.