[BOJ/16236] 아기 상어 - 풀이 및 코드

16236번: 아기 상어

흔히 아는 백상아리 상어는 너무 무섭네요... 귀여운 상어로 대체!!

문제

풀이

 구현 문제로, 요구사항을 정리하면 다음과 같습니다.

 아기 상어는 먹을 수 있는 물고기가 없으면 프로그램을 종료하고 정답을 출력한다.
정답은 아기 상어가 물고기를 먹으며 소모한 시간(초)이다.

아기 상어가 먹을 수 있는 물고기를 찾는 방법은 다음과 같다.
1. 현재 아기 상어의 위치에서 BFS를 진행한다.
2. BFS를 진행하며 아기 상어의 크기보다 큰 물고기는 통과할 수 없다. (큐에 삽입 X)
3. BFS를 진행하며 아기 상어의 크기보다 작거나 같은 물고기는 거리를 표시해둔다. (거리 갱신 및 큐 삽입)
4. 위 BFS 결과에서 가장 거리가 가까운 물고기를 골라 거리만큼 정답을 증가시키고 아기 상어의 위치를 그 물고기의 위치로 바꾼다.
5. 위 BFS 결과에서 먹을 수 있는 물고기가 없다면 프로그램을 종료한다.

  로직은 굉장히 단순합니다. BFS를 진행하여 먹을 수 있는 물고기를 식별하고 그 중 거리가 가장 가까우며 좌표가 좌상단에 가까운 물고기를 골라 해당 위치로 가는 비용을 정답에 계속 더해가면 되는 문제입니다. 하지만 신경써야할 것이 꽤 많은데 다음과 같은 것들을 신경써서 코드를 작성하면 큰 어려움 없이 문제를 푸실 수 있습니다.

 

1. 먹은 물고기는 더이상 먹으면 안된다. 따라서 그것을 식별할 정보가 필요하다.
2. 물고기를 먹은 뒤 해당 위치로 이동한다. 따라서 BFS를 진행할 때 시작 위치가 계속 바뀐다.
3. 물고기를 먹은 뒤 먹은 물고기의 개수가 현재 물고기의 크기와 같아지면 상어의 크기가 1씩 커진다.

 위 주의사항을 잘 지키며 구현해내면 큰 무리없이 풀 수 있다.

 

코드

BOJ 코드 치팅은 제재 대상입니다.

 

import sys
from collections import deque
input = sys.stdin.readline
INT_MAX = sys.maxsize

n = int(input().rstrip())
grid = [list(map(int, input().rstrip().split())) for _ in range(n)]
dirs = ((1, 0), (-1, 0), (0, 1), (0, -1))

# 최초의 상어 위치 및 물고기 정보 기록
r, c = 0, 0
for i in range(n):
    flag = False
    for j in range(n):
        if grid[i][j] == 9:
            r, c = i, j
            grid[i][j] = 0
            flag = False
            break
    if flag:
        break


def bfs(r, c):
    global dists, visited, curr_size, eatable_fishes, eaten_fishes
    q = deque()
    q.append((r, c))
    cost = 0
    while q:
        cost += 1
        for _ in range(len(q)):
            i, j = q.popleft()
            for di, dj in dirs:
                ni, nj = i + di, j + dj
                if ni < 0 or nj < 0 or ni >= n or nj >= n:
                    continue
                # 자신보다 작거나 같으면 통과 가능
                if not visited[ni][nj] and curr_size >= grid[ni][nj]:
                    visited[ni][nj] = True
                    dists[ni][nj] = cost
                    q.append((ni, nj))
                    # 먹지 않았으며 먹을 수 있다면 기록
                    if grid[ni][nj] != 0 and curr_size > grid[ni][nj] and (ni, nj) not in eaten_fishes:
                        eatable_fishes.append((cost, (ni, nj)))


ans = 0
ate_cnt = 0
curr_size = 2
eaten_fishes = set()

while True:
    # 상어 위치에서 BFS 진행하여 물고기 정보 갱신
    visited = [[False for _ in range(n)] for _ in range(n)]
    dists = [[INT_MAX for _ in range(n)] for _ in range(n)]
    visited[r][c] = True
    dists[r][c] = 0
    eatable_fishes = []
    bfs(r, c)
    # 먹을 수 있는 물고기를 오름차순 정렬 (비용, row, column)
    eatable_fishes.sort(key=lambda x: [x[0], x[1][0], x[1][1]])

    if eatable_fishes:
        cost, location = eatable_fishes[0]
        i, j = location
        ans += cost
        ate_cnt += 1
        eaten_fishes.add((i, j))
        r, c = i, j
    else:
        break

    # 섭취 후 크기 증가
    if ate_cnt == curr_size:
        curr_size += 1
        ate_cnt = 0

print(ans)

참고자료

https://highlaw00-dev.tistory.com/36

[알고리즘] 시뮬레이션 - dx, dy 기법

좌표계 문제를 풀 때 용이한 dx, dy 기법을 포스팅 해두었습니다.