백준 - [Gold 5] 16236번 아기 상어

문제링크: https://www.acmicpc.net/problem/16236

16236번: 아기 상어

삼성 기출로 나왔던 문제입니다. 삼성 기출은 조건 확인을 확실히 해주셔야 합니다.

---

문제 설명

- N: 맵의 크기

- 아기 상어 초기 크기 = 2  / 크기 만큼 물고기를 먹어야 => 크기 + 1 / 상어 위치 = 9

- 지나갈 수 있는 경우: 아기 상어 크기 >= 물고기 크기

- 먹을 수 있는 경우: 아기 상어 크기 > 물고기 크기

- 먹을 수 있는 경우가 여러가지인 경우 1. 거리 2. 위쪽 3. 왼쪽 순으로 방문

- 아기 상어가 먹을 수 없는 경우 이동한 거리만큼 출력

- ex) 아래 예시

1. 9에서 시작해서 오른쪽 상단 1방문 => +3
2. 왼쪽 하단 1방문 => + 6  상어 크기 3으로 증가
3. 왼쪽 하단 2방문 => + 1
4. 오른쪽 상단 2 방문 => +4
5. 더이상 먹을 수 없음 (크기는 3인데 남은 최솟값이 3부터임) => 14가 정답!

 

주요한 설명은 저정도 인 것 같습니다. 나머지는 문제를 참조해주세요!

---

풀이

일단 기본적으로 BFS를 사용합니다.

또한 거리순 위쪽 왼쪽 순으로 먹을 수 있는 경우의 수를 우선순위를 줘야하기 때문에 heapq를 사용합니다.

그리고 물고기를 먹었을 경우 방문 배열이나 큐를 초기화 해주는 것이 주의할 점입니다.

나머지는 조건을 잘 체크해야 하는 문제입니다. 코드 주석을 참조해주세요!

 

코드

import sys
from heapq import heappush, heappop

direction = ((0, 1), (1, 0), (0, -1), (-1, 0))
def bfs(distance, x, y):

    # 초기 아기상어
    size = 2 # 크기
    up = 0 # 먹은 횟수
    answer = 0 # 정답

    queue = []
    # heapq를 사용해서 거리순 x(위쪽) y(왼쪽) 순으로 정렬하면서 추가
    heappush(queue, (distance, x, y))
    visited = [[False] * N for _ in range(N)]

    while queue:
        
        distance, x, y = heappop(queue)

        # 먹을 수 있으면
        if 0 < MAP[x][y] < size:
            up += 1
            MAP[x][y] = 0
            # 다 먹었을 경우 크기 1개 증가 후 초기화
            if up == size:
                size += 1
                up = 0
            # 정답에 거리만큼 추가 후 초기화
            answer += distance
            distance = 0
            # 나머지 큐들 초기화
            while queue:
                print("초기화")
                queue.pop()
            # 방문 배열 초기화
            visited = [[False] * N for _ in range(N)]

        # 4 방향 탐색
        for d in direction:
            nx = x + d[0]
            ny = y + d[1]
            # 맵 안에 있고 지나갈 수 있으면(물고기의 크기 <= 상어의 크기)
            # 방문하지 않았을 경우
            if 0 <= nx < N and 0 <= ny < N and MAP[nx][ny] <= size\
                and not visited[nx][ny]:
                visited[nx][ny] = True
                heappush(queue, (distance + 1, nx, ny))
    
    print(answer)

sys.stdin = open("input.txt", "r")

# N, M 입력 
N = int(sys.stdin.readline())

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

for i in range(N):
    for j in range(N):
        if MAP[i][j] == 9:
            MAP[i][j] = 0
            bfs(0, i, j) # 거리, x, y

 

저도 rebas.kr/714 이 블로그를 참고하여서 풀었습니다. bfs를 응용한 문제로 heapq를 사용하고 초기화 시점을 잘 설정해주는 것이 핵심이였던 것 같습니다. 감사합니다.