[221010] 백준 16236 : 아기 상어

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

16236번: 아기 상어

1. 흐름도

 해당 문제를 보고 떠오른 흐름도다. 용어는 다음과 같다.

• f_size : 물고기 크기
• s_size : 상어 크기

 먼저 상어 크기보다 작은 물고기 그룹을 탐색해준다. 그리고 상어가 먹을 수 있는 물고기의 위치를 그룹화 한 뒤, 거리를 탐색한다. 거리 탐색 결과가 존재하는 경우, 상어는 최단거리로 이동하여 먹이를 먹고, 상어 크기를 확인한다. 크기가 커지지 않았다면 먹은 위치에서 거리 탐색을 다시 한다. 

 이때, 상어 크기가 커지는 경우에는 먹을 수 있는 물고기 수가 많아지기 때문에 그룹 탐색부터 다시 해주면서 반복한다. 해당 과정은 물고기가 없거나, 먹을 수 없는 경우가 될 때까지 실시한다.

 

2. 먹을 수 없는 경우?

 문제 다 풀어놓고, 해당 조건 때문에 1시간 헤맸다. 먹을 수 없는 경우란, 분명히 먹을 수 있는 물고기가 존재함에도 불구하고 상어가 도달하지 못하는 경우를 말한다. 다음과 같은 경우를 생각해보자. 

 9번은 상어, 나머지 숫자는 물고기의 크기인데, 현재 크기가 1인 물고기가 3인 물고기에 둘려쌓여있다. 상어 크기가 2라고 했을 때, 그룹 탐색을 통해 먹을 수 있는 물고기를 찾아냈지만, 거리 탐색 결과에는 반영하지 못한다. 흐름도에서는 "거리 탐색 결과 존재"라고 명시를 해놓았다. 이 점을 간과하면 런타임 에러(IndexError)가 발생하게 된다.

 

3. 전체 코드

메모리 : 125244 KB, 시간 : 1332 ms, 풀이 시간 : 86분

문제를 잘 읽고 반례를 충분히 생각하자

 

N = int(input())
board = [list(map(int, input().split())) for _ in range(N)]
f_info = {1 : [], 2 : [], 3 : [], 4 : [], 5 : [], 6 : []}
result = 0
for i in range(N):
    for j in range(N):
        if board[i][j] == 9 :
            s_info = [2, i, j, 0]
            board[i][j] = 0
        if 1 <= board[i][j] <= 6 :
            f_info[board[i][j]].append([i, j])

def bfs(queue):
    global result
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    while True :
        size = len(queue)
        temp = []
        if size == 0 : break
        for i in range(size):
            ex, ey = queue[i]
            visited = [[False for _ in range(N)] for _ in range(N)]
            q = [[s_info[1], s_info[2], 0]]
            visited[s_info[1]][s_info[2]] = True
            # Calc. Distance
            while q :
                x, y, cnt = q[0]
                del q[0]
                if [x, y] == [ex, ey] :
                    temp.append([cnt, x, y])
                    break
                for d in range(4):
                    nx = x + dx[d]
                    ny = y + dy[d]
                    if 0 <= nx < N and 0 <= ny < N and not visited[nx][ny] :
                        if board[nx][ny] <= s_info[0] :
                            q.append([nx, ny, cnt + 1])
                            visited[nx][ny] = True
        if temp :
            temp.sort()
            result += temp[0][0]
            queue.remove([temp[0][1], temp[0][2]])
            f_info[board[temp[0][1]][temp[0][2]]].remove([temp[0][1], temp[0][2]])
            s_info[1], s_info[2] = temp[0][1], temp[0][2]
            board[temp[0][1]][temp[0][2]] = 0
            s_info[3] += 1
        else :
            return False
        if s_info[3] == s_info[0]:
            s_info[0] += 1
            s_info[3] = 0
            break
    return True

def solve():
    # 먹을 수 있는 물고기 카운트
    while True :
        shark_size = s_info[0]
        tmp_q = []
        for fish_num in range(1, 7):
            if fish_num < shark_size :
                if f_info[fish_num] :
                    tmp_q += f_info[fish_num]
        if not tmp_q : break
        if not bfs(tmp_q) : break

solve()
print(result)