문제

링크

복습 요망!

풀이

쉽지 않은 문제였다. 전부터 시뮬레이션, 구현 문제에 어려움을 느꼈는데, 극복 and 정복하도록 더 열심히 해야겠다...

시뮬레이션 문제는 주어진 조건과 진행방식을 따라서 차근차근 구현하면 된다. 조건과 탐색을 진행하는 코드의 순서와 방식이 중요하다고 생각한다.

1. 아기 상어의 시작점을 구하고 큐에 넣는다.

2. 현재 아기 상어의 위치에서 최단거리를 구하는 테이블을 생선한다.

3. 생성된 거리테이블과 물고기 크기테이블을 통해 최단거리에 있고 먹을 수 있는 물고기를 찾아 먹은 후 걸린 시간을 계산한다.

4. 먹을 물고기가 없거나 존재하지 않을 때까지 위 과정을 반복한다.

코드

import sys
from collections import deque

input = sys.stdin.readline
N = int(input())
aqua = [list(map(int, input().split())) for _ in range(N)]

size = 2
sx, sy = 0, 0
# 아기상어 출발 시작점 찾기 (1번만 수행)
for r in range(N):
    for c in range(N):
        if aqua[r][c] == 9:
            sx, sy = r, c
            aqua[r][c] = 0

dir = [[-1, 0], [1, 0], [0, -1], [0, 1]]


# 현재 아기상어 위치에서 최단거리 테이블을 계산하는 함수
def bfs():
    distance = [[-1] * N for _ in range(N)]
    q = deque([(sx, sy)])
    distance[sx][sy] = 0
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x + dir[i][0]
            ny = y + dir[i][1]
            if 0 <= nx < N and 0 <= ny < N:
                if distance[nx][ny] == -1 and aqua[nx][ny] <= size:
                    distance[nx][ny] = distance[x][y] + 1
                    q.append((nx, ny))

    return distance


# 계산된 거리테이블과 크기테이블을 통해 먹을 물고기 탐색 (공간안에 있고 아기상어 크기보다 작은 물고기만 먹게)
def hunt(distance):
    minimum = 1e9
    x, y = 0, 0
    for i in range(N):
        for j in range(N):
            if distance[i][j] != -1 and 1 <= aqua[i][j] < size:
                if distance[i][j] < minimum:
                    x, y = i, j
                    minimum = distance[i][j]

    if minimum == 1e9:
        return 0
    else:
        return x, y, minimum

answer = 0
count = 0
while True:
    fish = hunt(bfs())
    if fish == 0:
        print(answer)
        break
    else:
        sx, sy = fish[0], fish[1]
        answer += fish[2]
        aqua[sx][sy] = 0
        count += 1
        if count == size:
            size += 1
            count = 0