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

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

16236번: 아기 상어

---

아이디어

1. 최소 경로 bfs

• 지도와 최소 경로가 필요하다는 것을 보고 bfs를 사용하기로 결정.
• 여유로운 시간과 n크기를 보고 bfs를 여러 번 해도 괜찮겠다고 생각했다.
• 그래서 가장 가까운 먹이를 찾을 때마다 bfs를 사용하기로 했다.

2. 가장 가까운 물고기

• a. 물고기까지 이동이 가능한지 check
• b. 그 물고기를 먹을 수 있는지
• c. 가능한 물고기들을 리스트에 담아두고 lambda 함수를 써서 거리순, 가장 위쪽 순, 가장 왼쪽 순으로 정렬한다.

---

코드 설명

for i in range(N):
    room.append([int(x) for x in sys.stdin.readline().rstrip().split()])
    for j in range(len(room[i])):
        if room[i][j] == 9:
            room[i][j] = 0
            shark_x, shark_y = i, j

먼저 공간에 대한 정보를 받아온다 그리고 상어의 초기 좌표는 따로 저장해 두고 상어가 있던 칸은 비워둔다.

 

def finding_fish(sx,sy):
    global sharksize
    deq = deque()
    deq.append([sx,sy])

    visited = [[False for _ in range(N)] for _ in range(N)]
    distance = [[0 for _ in range(N)] for _ in range(N)]
    can_eat_fish = []

    while deq:
        x, y = deq.popleft()

        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx < N and 0 <= ny < N:
                if room[nx][ny] <= sharksize and not visited[nx][ny]: #이동이 가능하면
                    visited[nx][ny] = True
                    distance[nx][ny] = distance[x][y] + 1
                    deq.append([nx,ny])

                    if room[nx][ny] < sharksize and room[nx][ny] != 0: #물고기가 있고 그걸 먹을 수 있다면
                        can_eat_fish.append([nx ,ny,distance[nx][ny]])

    can_eat_fish.sort(key= lambda x : (x[2],x[0],x[1])) # 정렬은 거리, x, y 오름차순으로
    return can_eat_fish

물고기를 찾는 방법이다. 

상어의 좌표에서 시작해 bfs방식으로 찾아가면 된다.

 

상하좌우로 탐색을 하면서 먼저 경곗값을 확인해준다.

그다음 이동이 가능한지 확인해주고 가능하다면 방문을 체크하고 좌표를 큐에 추가해준다.

 

만약 이동했는데 거기에 물고기가 있고 먹을 수 있다면, 먹을 수 있는 물고기 리스트(can_eat_fish) 리스트에 추가해준다.

리스트에는 물고기의 x, y 좌표와 상어와의 거리(distance)를 저장해준다.

 

bfs탐색이 끝나면 물고기 리스트를 거리, x좌표, y좌표 오름차순으로 정렬해준다.

 

최종으로 리스트를 return 해주면 준비는 끝이다.

 

 

if __name__ == '__main__':
    ans = 0

    while True:
        fishlist = finding_fish(shark_x,shark_y)

        if len(fishlist) == 0: # 먹을 수 있는 물고기가 없다면
            print(ans)
            exit(0)

        shark_x, shark_y, move_time = fishlist[0]

        sharkeat += 1
        if sharksize == sharkeat: #먹은 물고기수와 사이즈가 같다면
            sharkeat = 0
            sharksize += 1

        room[shark_x][shark_y] = 0 # 물고기 먹은 자리는 빈칸으로 바꿈
        ans += move_time

 

물고기 리스트를 받아왔는데 리스트가 비어 있다면 먹을 수 있는 물고기가 더 이상 없다는 뜻이므로 

답을 출력하고 종료하면 된다.

 

물고기가 리스트에 있다면 상어의 좌표는 그 물고기의 좌표로 변경시켜준다.

거리가 곧 시간(1칸에 1초)이므로 거리만큼 시간에 추가해주면 된다.

 

이후 상어가 먹은 물고기 수와 크기를 업데이트해주고 물고기가 있던 자리는 빈칸으로 바꿔준다. 

---

전체 코드

import sys
from collections import deque
N = int(input())

dx = [-1,0,0,1] # 상 좌 우 하
dy = [0,-1,1,0]
room = []
sharksize = 2
sharkeat = 0

for i in range(N):
    room.append([int(x) for x in sys.stdin.readline().rstrip().split()])
    for j in range(len(room[i])):
        if room[i][j] == 9:
            room[i][j] = 0
            shark_x, shark_y = i, j

def finding_fish(sx,sy):
    global sharksize
    deq = deque()
    deq.append([sx,sy])

    visited = [[False for _ in range(N)] for _ in range(N)]
    distance = [[0 for _ in range(N)] for _ in range(N)]
    can_eat_fish = []

    while deq:
        x, y = deq.popleft()

        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx < N and 0 <= ny < N:
                if room[nx][ny] <= sharksize and not visited[nx][ny]: #이동이 가능하면
                    visited[nx][ny] = True
                    distance[nx][ny] = distance[x][y] + 1
                    deq.append([nx,ny])

                    if room[nx][ny] < sharksize and room[nx][ny] != 0: #물고기가 있고 그걸 먹을 수 있다면
                        can_eat_fish.append([nx ,ny,distance[nx][ny]])

    can_eat_fish.sort(key= lambda x : (x[2],x[0],x[1])) # 정렬은 거리, x, y 오름차순으로
    return can_eat_fish

if __name__ == '__main__':
    ans = 0

    while True:
        fishlist = finding_fish(shark_x,shark_y)

        if len(fishlist) == 0: # 먹을 수 있는 물고기가 없다면
            print(ans)
            exit(0)

        shark_x, shark_y, move_time = fishlist[0]

        sharkeat += 1
        if sharksize == sharkeat: #먹은 물고기수와 사이즈가 같다면
            sharkeat = 0
            sharksize += 1

        room[shark_x][shark_y] = 0 # 물고기 먹은 자리는 빈칸으로 바꿈
        ans += move_time