개구리

우물 안 개구리

BFS를 사용하는 구현 문제이다. 조건이 다양하기 때문에 주의해서 풀어야 한다.

#아기 상어 (BFS, 구현)
from collections import deque

N = int(input())
sea = [ ] # 격자 저장
shark = [] # 상어 시작 위치 저장

for i in range(N):
    line = list(map(int, input().split()))
    sea.append(line)
    for j in range(N):
        if line[j] == 9 :
            shark =[i,j]
        elif line[j] !=0 :
            pass

dx=[-1,0,0,1]
dy=[0,-1,1,0]
sol = 0
size = 2
sea[shark[0]][shark[1]]=0
eaten = [0 for _ in range(8)]

#현재 기준 먹을 수 있는 물고기 위치 배열 리턴
def BFS(x,y,size):
    
    visited=[[-1 for _ in range(N)]for _ in range(N)]
    visited[x][y]=0
    
    fish=[]
    q= deque([[x,y]])
    idx = [x,y]
    while (q):
        ax, ay = q.popleft()    
        for i in range(4):
            nx, ny = ax+dx[i], ay+dy[i]
            
            
            if 0<=nx<N and 0<=ny<N and visited[nx][ny]==-1:
                if sea[nx][ny] <=size:
                    visited[nx][ny]=visited[ax][ay]+1
                    q.append([nx,ny])            
                    if 0<sea[nx][ny] < size :
                        fish.append([nx,ny, visited[nx][ny]])
                
        if idx==[ax,ay]: #한 바퀴 돌았을 때
            if fish!=[]: # 채워지면 종료
                return fish
            if q!=deque([]):
                idx=q[-1]
    return fish

while True:
    
    fish = BFS(shark[0], shark[1], size)
    
    if fish ==[]: # 더 이상 먹을 수 없다면 종료
        break
    
    fish.sort(key = lambda x:(x[0],x[1]))
    target = fish[0]
    sea[target[0]][target[1]]=0
    sol = sol + target[2]
    eaten[size] +=1
    
    if eaten[size]==size and size<=6:
        size+=1
    shark=target # 먹은 위치에서 다시 시작

print(sol)

풀이

아기 상어의 위치에서 BFS를 통해 최단 거리에 있는 물고기를 탐색한다. 대부분 풀이를 보면 아기 상어가 먹을 수 있는 모든 물고기를 탐색하는 것 같다. 하지만 물고기를 탐색할 때 모든 격자를 탐색하지 않고 최단 거리에 있는 물고기를 탐색하면 해당 단계의 BFS만 완료하고 반환하면 된다.

아기 상어의 크기를 갱신해주면서 물고기를 더 이상 먹을 수 없을 때까지 반복문을 진행한다.

문제 설계

  1. sea 배열에 입력값으로 주어진 격자를 그대로 저장한다. shark에 아기 상어의 초기 위치를 저장하고. size에 아기 상어의 크기인 2를 저장한다.
  2. sea 격자에서 아기 상어의 초기 위치에 해당하는 값을 0으로 저장한다. BFS를 돌리며 크기가 9인 물고기로 인식하지 않도록 하기 위함이다.
  3. 아기 상어의 크기에 따라 먹은 물고기 수를 eaten 배열에 저장한다. (굳이 배열을 사용하지 않고 아기 상어의 크기와 현재 먹은 물고기 수를 계속해서 갱신해가며 비교하는 방법도 있다.)

BFS 구현

  • 현재 아기 상어의 크기와 방문 하려는 칸의 물고기의 크기를 비교해야 한다.
  • 최단 거리에 있는 물고기가 여러 마리인 경우가 있기 때문에 같은 단계의 BFS를 모두 실행해야 한다.
  • BFS를 모두 실행하는 것을 표시하기 위해 idx에 큐의 마지막 원소를 저장하고 해당 원소가 pop된다면 같은 단계의 BFS가 모두 실행되었다는 것을 알 수 있다.
    1. 현재 아기 상어의 위치를 기준으로 네 방향을 탐색한다. (이 때 탐색하는 순서만으로는 주어진 가장 위쪽, 가장 왼쪽의 조건을 해결할 수 없다.)
    2. 인접한 칸에 방문한 적이 없고 현재 아기 상어의 크기가 물고기보다 크거나 같다면 해당 칸에 방문할 수 있다.
    3. 방문할 수 있을 때 아기 상어의 크기가 물고기보다 크다면 해당 물고기를 먹을 수 있으므로 fish 배열에 위치를 저장한다.
    4. 만약 BFS를 한 단계 돌렸을 때 fish 배열이 빈 배열이라면 다시 idx를 갱신하고 BFS를 한 단계 더 실행하고, fish 배열이 빈 배열이 아니라면 이를 반환한다.

전체 로직 구현

  1. 아기 상어가 물고기를 잡아 먹은 칸을 시작 지점으로 갱신하고 다시 BFS를 실행한다. 더 이상 먹을 수 있는 물고기가 없을 때까지 반복한다.
  2. BFS를 통해 최단 거리에 있는 물고기들의 위치와 해당 지점까지 이동한 거리가 담긴 배열을 얻는다.
  3. 가장 위쪽에 있는 순서대로, 가장 왼쪽에 있는 순서대로 정렬한 뒤 한 마리의 물고기를 먹는다. 이 때 물고기의 위치를 sea 격자에서 0으로 갱신한다.
  4. sol에 해당 물고기까지 오는 데 소요된 거리(시간)를 더해준다.
  5. eaten 배열에서 현재 크기일 때 잡아 먹은 물고기의 수를 1 더해준다.
  6. 만약 현재 크기만큼 물고기를 잡아 먹었다면 아기 상어의 크기가 1만큼 커진다.
  7. 반복문이 종료되면 sol을 출력한다.

댓글남기기

참고