[백준] CLASS 4 달성하기 2일차

이진규·2022년 7월 27일
1

백준(PYTHON)

목록 보기
58/115

1. 아기상어(★BFS)

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

from collections import deque
from sys import stdin
input = stdin.readline

n = int(input())
graph = [ list(map(int, input().split())) for _ in range(n) ]

x, y, size = 0, 0, 2
for i in range(n): # 아기 상어의 위치를 찾고 아기상어 위치 좌표와 사이즈(2) 초기화
    for j in range(n):
        if graph[i][j] == 9:
            x, y = i, j
            break

dx, dy = [0, 0, -1, 1], [-1, 1, 0, 0]
def biteFish(x, y, shark_size):
    distance = [ [0] * n for _ in range(n) ]
    visited = [ [False] * n for _ in range(n) ]

    q = deque()
    q.append((x, y))
    visited[x][y] = True
    temp = [] # 상어가 먹잇감을 마주 쳤을때 해당 좌표와 움직인 거리 : (먹잇값의 좌표, 움직인 거리)

    while q:
        px, py = q.popleft()

        for k in range(4):
            mx = px + dx[k]
            my = py + dy[k]

            if 0 <= mx < n and 0 <= my < n and not visited[mx][my]:
                if graph[mx][my] <= shark_size:
                    q.append((mx, my))
                    visited[mx][my] = True
                    distance[mx][my] = distance[px][py] + 1
                    if graph[mx][my] < shark_size and graph[mx][my] != 0: # 상어가 실제 먹잇감을 발견했을 때 해당 좌표와 이때까지 움직인 거리 기록
                        temp.append((mx, my, distance[mx][my]))

    # 거리가 가까운 물고기가 많다면 가장 위에 있는 물고기, 그러한 물고기가 여러마리라면 가장 왼쪽에 물고기를 먹도로 좌표를 정렬한다.
    # 거리순 x[2] 으로 정렬 후 x[0], x[1] 순으로 정렬한다면 가장 위, 가장 왼쪽의 물고기 좌표가 먼저오도록 설정된다.
    return sorted(temp, key=lambda x : (x[2], x[0], x[1]))

cnt = 0
result = 0
while 1:
    shark = biteFish(x, y, size)

    # 더이상 먹을 수 있는 물고기가 없다면 엄마상어에게 도움 요청
    if len(shark) == 0:
        break

    # 가장 가까이 있는 물고기중 가장 위쪽, 가장 왼쪽에 있는 물고기를 꺼낸다.
    mx, my, dist = shark.pop(0)

    # 움직이는 거리 = 걸린 시간
    result += dist
    # 상어의 처음위치랑, 상어가 물고기를 잡아먹고 난 뒤의 좌표는 0으로 초기화 한다.
    graph[x][y], graph[mx][my] = 0, 0

    # 상어의 처음 위치를 물고기를 잡아먹고 난 뒤의 좌표로 옮겨준다.
    x, y = mx, my
    # 물고기를 잡아먹은 횟수
    cnt += 1

    # 물고기를 잡아먹은 횟수와 상어의 사이즈가 같다면 사이즈를 높여주고 잡아먹은 횟수는 다시 초기화
    if cnt == size:
        size += 1
        cnt = 0

print(result)
profile
항상 궁금해하고 공부하고 기록하자.

0개의 댓글