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

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

16236번: 아기 상어

문제



 

공간과 아기상어, 먹이가 주어질 때 아기상어가 물고기를 잡아먹을 수 있는 최단시간을 구하는 문제이다.

---

풀이

먼저 먹을 수 있는 물고기가 1마리보다 많다면, 거리가 가장 가까운 물고기를 먹으러간다. 라는 조건이 있다.

따라서 BFS를 사용하는데 이는 BFS가 최단경로를 가지기 때문이다.

 

이를 해결하기 위해 다음과 같은 순서를 사용하였다.

1. BFS를 사용하여 현재 위치에서 각 위치까지의 최단거리를 계산한다.

2. BFS에서 조건은 다음과 같다.

   1. space의 범위를 확인한다.

   2. 상어의 크기가 물고기 크기보다 크거나 같은지 확인한다.

   3. 방문여부를 확인한다.

   4. visited에 +1을 한다.

3. 최종적으로 BFS의 결과를 반환하여 먹을 수 있는 물고기 중 가장 가까운 물고기를 찾는다.

 

#상어의 초기 위치를 저장 후 0으로 초기화
for i in range(N):
    for j in range(N):
        if space[i][j] == 9:
            nowX, nowY = i, j
            space[i][j] = 0

먼저 상어의 위치를 저장하고 0으로 초기화 해준다.

#현재 위치에서 각 물고기까지의 거리를 반환
def BFS():
    q = deque([(nowX, nowY)])
    visited = [[-1] * N for _ in range(N)]
    visited[nowX][nowY] = 0
    
    while q:
        x, y = q.popleft()
        
        for i in range(4):
            nx, ny = x + dx[i] , y + dy[i]
            
            if 0 <= nx < N and 0 <= ny < N:
                if size >= space[nx][ny] and visited[nx][ny] == -1:
                    visited[nx][ny] = visited[x][y] + 1
                    q.append((nx, ny))
                    
    return visited

BFS에서는 현재 위치에서 각 물고기까지의 거리를 반환한다. 이 때 BFS를 사용하므로 각 거리는 최단거리가 된다.

 

# 먹을 물고기를 찾는다.
def solve(visited):
    x, y = 0, 0
    minDistance = INF
    for i in range(N):
        for j in range(N):
            #BFS에서 지나지 않는 경로는 최단경로가 아니다 + 아기 상어가 먹을 수 있는지 확인
            if visited[i][j] != -1 and 1 <= space[i][j] < size:
                if visited[i][j] < minDistance:
                    minDistance = visited[i][j]
                    x, y = i, j
    #탐색후에도 INF값이면 먹을 물고기가 없다.
    if minDistance == INF:
        return False
    else:
        return x, y, minDistance

solve함수는 먹을 물고리를 찾는다.

BFS에서 반환한 visited를 가지고 BFS가 지났으면서 상어가 먹을 수 있는지 검사한다.

만약 조건을 만족하면 거리를 증가시키고 x, y값을 할당해준다.

 

마지막으로 x, y, 최단거리를 반환한다.

 

answer = 0
food = 0

while True:
    result = solve(BFS())
    
    if not result:
        print(answer)
        break
    else:
        nowX, nowY = result[0], result[1]
        answer += result[2]
        space[nowX][nowY] = 0
        food += 1
        
    if food >= size:
        size += 1
        food = 0

 

최종적으로 먹을 수 있는 물고기 중 가장 가까운 물고기를 찾고, 먹으러 가면 된다.

 

코드

from collections import deque
N = int(input())
space = [list(map(int, input().split())) for _ in range(N)]

size = 2
INF = 1e9

nowX, nowY = 0, 0

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

#상어의 초기 위치를 저장 후 0으로 초기화
for i in range(N):
    for j in range(N):
        if space[i][j] == 9:
            nowX, nowY = i, j
            space[i][j] = 0


#현재 위치에서 각 물고기까지의 거리를 반환
def BFS():
    q = deque([(nowX, nowY)])
    visited = [[-1] * N for _ in range(N)]
    visited[nowX][nowY] = 0
    
    while q:
        x, y = q.popleft()
        
        for i in range(4):
            nx, ny = x + dx[i] , y + dy[i]
            
            if 0 <= nx < N and 0 <= ny < N:
                if size >= space[nx][ny] and visited[nx][ny] == -1:
                    visited[nx][ny] = visited[x][y] + 1
                    q.append((nx, ny))
                    
    return visited

# 먹을 물고기를 찾는다.
def solve(visited):
    x, y = 0, 0
    minDistance = INF
    for i in range(N):
        for j in range(N):
            #BFS에서 지나지 않는 경로는 최단경로가 아니다 + 아기 상어가 먹을 수 있는지 확인
            if visited[i][j] != -1 and 1 <= space[i][j] < size:
                if visited[i][j] < minDistance:
                    minDistance = visited[i][j]
                    x, y = i, j
    #탐색후에도 INF값이면 먹을 물고기가 없다.
    if minDistance == INF:
        return False
    else:
        return x, y, minDistance
    
answer = 0
food = 0

while True:
    result = solve(BFS())
    
    if not result:
        print(answer)
        break
    else:
        nowX, nowY = result[0], result[1]
        answer += result[2]
        space[nowX][nowY] = 0
        food += 1
        
    if food >= size:
        size += 1
        food = 0