16236번 - 아기 상어

문제

 

16236번: 아기 상어 (acmicpc.net)

16236번: 아기 상어

풀이 1

총 두가지 방법으로 시도했다. 첫 번째는 미리 먹잇감들의 좌표들을 집합안에 넣어놓고 아기상어가 잡아먹을 때 마다 해당 좌표를 집합에서 제거하는 방식이고, 두 번째는 매번 남아 있는 먹잇감을 전부 탐색하는 방식이다. 결과 부터 말하자면 두 번째 방식이 훨씬 적은 실행속도를 보여줬는데, 그 이유는 보드 위에 빈칸(0) 이 압도적으로 많지 않은 이상 미리 집합안에 좌표를 넣어놓나 매번 탐색하나 탐색연산에 큰 차이가 없을 뿐더러, 아기 상어가 먹이를 먹을 때 마다 집합의 제거 연산과 함수 호출 횟수만 늘어나기 때문이라 추측된다. 확실한것은, 위와 같은 상황, 즉 탐색 풀을 집합안에 미리 넣어놨을 때 시간적으로 큰 이득을 볼 수 있는 상황이 자명하지 않다면 매번 새로 탐색하는것이 유리하다는 것이다. 앞으로 문제풀이에 지침으로 삼고 가야겠다. 또한 BFS로 풀며 매우 큰 교훈을 얻었는데, 방문처리를 비롯한 모든 처리는 큐에 넣고 빼기 전에 처리해야 한다는 것이다. 무슨말 이냐면, 이런 경우를 마주했다. 아래 주석을 참고하자. DFS도 마찬가지라고 생각되는데, DFS 는 반대로 방문처리를 스택에서 꺼낸 후에 하기 때문에, 모든 처리를 스택에서 꺼낸 후에 하면 되겠다. 마지막으로, 문제좀 제대로 읽을 필요가 있다. 그것도 아주.... 잘!!!

# 평범한 BFS
def get_preys(bLoc,bSize):
    heap = []
    q = deque()
    q.append((*bLoc,0))
    visited = set()
    visited.add(bLoc)
    while q:
        row,col,cnt = q.popleft()
        # 여기서 방문처리하면 무한 루프
        # 여기서 heappush 하면 무한 루프
        for i in range(4):
            nRow,nCol = row+dRow[i],col+dCol[i]
            if 0 <= nRow < n and 0 <= nCol < n and not (nRow,nCol) in visited:
                if board[nRow][nCol] <= bSize:
                	# 항상 큐에 넣기 전에 모든 처리를 실행할것!!!
                    if 0 < board[nRow][nCol] < bSize:
                        heapq.heappush(heap,((cnt+1,nRow,nCol)))
                    visited.add((nRow,nCol))
                    q.append((nRow,nCol,cnt+1))
    return heap[0] if heap else None

from collections import deque
import heapq

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

# 북 서 남 동
dRow = [-1,0,1,0]
dCol = [0,-1,0,1]

class BabyShark:
    def __init__(self,loc):
        self.size = 2
        self.loc = loc
        self.cnt = 0
    def eat(self,loc):
        self.loc = loc
        self.cnt += 1
        if self.cnt == self.size:
            self.cnt = 0
            self.size += 1


def get_preys(bLoc,bSize):
    heap = []
    q = deque()
    q.append((*bLoc,0))
    visited = set()
    visited.add(bLoc)
    while q:
        row,col,cnt = q.popleft()
        for i in range(4):
            nRow,nCol = row+dRow[i],col+dCol[i]
            if 0 <= nRow < n and 0 <= nCol < n and not (nRow,nCol) in visited:
                if board[nRow][nCol] <= bSize:
                    if 0 < board[nRow][nCol] < bSize:
                        heapq.heappush(heap,((cnt+1,nRow,nCol)))
                    visited.add((nRow,nCol))
                    q.append((nRow,nCol,cnt+1))
    return heap[0] if heap else None


def find_baby():
    for row in range(n):
        for col in range(n):
            if board[row][col] == 9:
                return (row, col)


baby = BabyShark(find_baby())
answer = 0

while True:
    prey = get_preys(baby.loc,baby.size)
    if not prey:
        break
    [cnt,nRow,nCol] = prey
    board[baby.loc[0]][baby.loc[1]], board[nRow][nCol] = 0, 9
    baby.eat((nRow,nCol))
    answer += cnt

print(answer)

풀이 2

BFS로 상어 위치를 기준으로 주변에 먹을 수 있는 물고기가 있는지 탐색하는데, 탐색한 물고기 heap에 담겨있는 물고기까지의 거리보다 큰 거리는 가지치기로 탐색하지 않는다.

먹을 수 있는 물고기가 탐색되지 않는다면 반복문을 탈출하고, 있다면 상어의 크기, 위치, 먹은 물고기의 수를 갱신한다.

from collections import deque
import heapq

dRow = [-1,0,1,0]
dCol = [0,-1,0,1]

N = int(input())
board = [[0]*N for _ in range(N)]
s_cnt = 0
s_size = 2
sr = 0
sc = 0
for i in range(N):
    for j,v in enumerate(map(int,input().split())):
        board[i][j] = v
        if v == 9:
            sr,sc = i,j

answer = 0
while True:
    # 물고기 탐색
    distance = [[0]*N for _ in range(N)]
    heap = []
    q = deque()
    q.append((sr,sc))
    while q:
        r,c = q.popleft()
        for i in range(4):
            nr,nc = r+dRow[i],c+dCol[i]
            if 0 <= nr < N and 0 <= nc < N and distance[nr][nc] == 0\
                    and board[nr][nc] <= 6 and board[nr][nc] <= s_size:
                distance[nr][nc] = distance[r][c] + 1
                # 가지치기
                if heap and distance[nr][nc] > heap[0][0]:
                    continue
                # 먹을 수 있는 물고기
                if 1 <= board[nr][nc] < s_size:
                    heapq.heappush(heap,(distance[nr][nc],nr,nc))
                q.append((nr,nc))
    if not heap:
        print(answer)
        break
    # 상어 이동
    td,tr,tc = heap[0]
    answer += td
    board[sr][sc],board[tr][tc] = 0,9
    s_cnt += 1
    if s_cnt == s_size:
        s_cnt = 0
        s_size += 1
    sr,sc = tr,tc