[16236] 아기상어 (Python)

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

16236번: 아기 상어

---

이 문제도 벽 부수고 이동하기 문제만큼이나 오랜 시간이 걸린 문제다.

 

문제

문제를 요약하면 다음과 같다

 

• n*n 크기의 공간에 물고기 m마리, 아기 상어 1마리가 있다 (아기상어와 물고기는 크기를 가짐)
• 아기상어는 1초에 상하좌우 중 하나 1칸을 이동하고 물고기를 먹으면 그 칸은 빈칸이 됨
• 아기상어의 초기 크기는 2
  
  • 아기상어 크기 > 물고기 크기 : 먹을 수 있고 지나갈 수 있음
  • 아기상어 크기 == 물고기 크기 : 지나갈 수 있음
  • 아기상어 크기 < 물고기 크기 : 모두 안됨
• 이동 방법
  • 더 이상 먹을 수 있는 물고기가 없다면 초를 출력
  • 먹을 수 있는 물고기가 1마리라면 그 물고기를 먹음
  • 먹을 수 있는 물고기가 여러개라면 가장 가까운 물고기를 먹고 거리가 같다면 가장 위, 가장 왼쪽 물고기를 먹음
• 아기상어는 자신의 크기와 같은 수의 물고기를 먹으면 크기가 1씩 증가

 

풀이

위 문제를 bfs 함수와 heapq을 사용하여 해결하였다.

먹을 수 있는 물고기가 여러마리인 경우 우선순위대로 먹기 위해 bfs를 사용하였다. 하지만 bfs를 사용하면 거리가 가장 가까운 물고기는 구할 수 있지만 ⬆️ ⬅️ ➡️ ⬇️ 순서로 탐색한다고 해도 무조건 위, 왼쪽이 먼저 실행되지 않는다.

 

예를 들어, 아래 공간을 (0,0) ~ (3,3) 까지라고 생각했을 때, (1,3)보다 (2,0)이 먼저 실행되는 문제가 발생한다.

따라서 heapq를 사용하여 (거리, x좌표, y좌표)를 넣어 거리가 가장 가까운순, 위, 왼쪽 순으로 실행되도록 하였다.

 

bfs로 탐색을 하면서 heapq에서 가장 작은 값을 꺼내 물고기의 크기와 상어의 크기를 비교하여 물고기를 잡아먹는 경우와 주변을 탐색하는 경우로 나누었다.

 

물고기를 잡아 먹는 경우, 물고기 수를 매번 count하고 조건에 따라 상어의 크기를 키웠다. 남은 물고기가 없거나 크기가 가장 작은 물고기가 상어보다 큰 경우 시간을 반환하면 된다.

물고기를 잡아먹었다면 다음에 먹을 물고기를 다시 찾아야하므로 heapq와 visited배열을 모두 초기화하여 다시 탐색해주었다.

 

주변을 탐색만 하는 경우 물고기 크기가 상어 크기보다 작거나 같고 방문하지 않았다면 heapq에 넣고 방문처리를 하였다.

 

 

풀이 1 : 시간 초과

1차 시도는 3%에서 시간초과가 발생했다. 이동할 때 이미 방문한 노드를 재방문하지 않도록 구현하였다. 방문 여부를 체크할 때, 리스트에 해당 노드가 있는지 not in 을 사용하여 체크하는 바람에 O(N)의 시간복잡도가 추가도 들어갔던 것 같다.

 

풀이 2 : 통과

이미 탐색한 위치를 visited 배열을 생성하여 체크하였으며 물고기를 잡아먹으면 visited 배열을 초기화하였다.

 

 

코드

아래의 더보기는 내가 코드를 구현한 방식이다.

입력

• 공간의 상태를 입력 받을 때 물고기의 크기(fish 배열)와 상어의 위치( posX, posY )를 따로 저장함
• fish 배열을 오름차순으로 정렬
• 위치 탐색 여부를 저장하는 visited 배열 생성

bfs 함수

• size(아기 상어 크기), count(상어 크기가 바뀐 후 잡아먹은 물고기 수), time(시간)

1. 아기 상어가 있던 위치를 0으로 바꾸고 방문 처리 후 heapq(최소 힙)에 (거리, x좌표-행, y좌표-열) 순으로 넣기
2. q에 값이 있다면 반복
   1. heap에서 가장 작은 값을 꺼냄
   2. 물고기를 잡아먹는 경우
      1. 물고기 수를 count / 조건을 만족하면 상어 크기를 키움 / fish배열에서 해당 크기의 물고기를 제거
      2. 남은 물고기를 더 이상 먹을 수 없다면 return time
         • len(fish) == 0 : 남은 물고기X
         • fish[0] >= size : 크기가 가장 작은 물고기가 상어보다 큰 경우
      3. 위치를 0으로 바꿈 / heap을 비움 / visited 배열 초기화
      4. 현재 위치는 방문 처리해줌
   3. 주변을 탐색하는 경우(이동)
      1. 물고기 크기 ≤ 상어 크기이고 방문하지 않았다면 heap에 넣고 방문 처리
3. 반복 끝나면 return time

main 코드

• 물고기가 없으면 0 출력
• 물고기가 있으면 bfs 함수 수행

 

 

import sys
import heapq

n = int(sys.stdin.readline())
area=[]
fish = []
for i in range(n):
    area.append(list(map(int,sys.stdin.readline().split())))
    for j in range(n):
        if area[i][j] == 9:
            posX = i
            posY = j
        elif area[i][j] != 0:
            fish.append(area[i][j])
fish.sort()
visited = [[False]*n for _ in range(n)]

dx=[-1,0,0,1]
dy=[0,-1,1,0]
# bfs 함수
def bfs(area,x,y,visited):
    q = []
    size = 2    # 아기 상어 크기
    count= 0    # 상어 크기가 바뀐 후 잡아먹은 물고기 수
    time = 0    # 시간
    area[x][y] = 0
    visited[x][y] = True
    heapq.heappush(q,(0,x,y))
    while q:
        lev,x,y = heapq.heappop(q)
        # 물고기를 잡아먹는 경우
        if 0 < area[x][y] < size:
            time = lev
            count += 1  # 물고기 수 count
            if count == size:   # 상어 크기 증가
                size += 1
                count = 0
            fish.remove(area[x][y])
            if len(fish)==0 or fish[0] >= size: # 남은 물고기를 더이상 먹을수 없다면 return
                return time
            area[x][y] = 0
            q = []
            visited = [[False]*n for _ in range(n)]
            visited[x][y] = True
        # 주변 탐색
        for i in range(4):
            nx = x+dx[i]
            ny = y+dy[i]
            if nx<0 or nx>=n or ny<0 or ny>=n:
                continue
            if area[nx][ny] <= size and not visited[nx][ny]:
                heapq.heappush(q,(lev+1,nx,ny))
                visited[nx][ny] = True
    return time

if len(fish) == 0:
    print(0)
else:
    print(bfs(area,posX,posY,visited))