Easy is Perfect

[백준] 16236번 아기 상어 _ 문제 풀이

  • melonicedlatte
  • Apr 24, 2021


1. 문제

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

2. 풀이

삼성 SW 역량테스트 문제입니다. 하기와 같이 풀이했습니다. 자세한 사항은 소스코드를 참고해주세요.

  • 상어가 갈 수 있는 공간을 찾을 때는 BFS 를 이용합니다.
    • 같은 거리에서 갈 수 있는 곳이 여러 곳이 있으면, 정렬하여 가장 앞에 있는 요소를 꺼냅니다. (행, 열)로 정렬한 경우 원하는 값이 나오게 됩니다.
  • 좌표를 이동할 때, 사라지는 물고기와 상어의 index 변경을 잊지 말고 체크해주어야합니다.
# 패키지
from collections import deque
# 상수
SHARK = 9
# 변수
N = int(input())
maps = [list(map(int, input().split())) for _ in range(N)]
ate_num = 0
shark_size = 2
shark = []
# 상우하좌
dr = [-1, 0, 1, 0]
dc = [0, 1, 0, -1]
total_time = 0

# bfs 방식을 이용 : 가장 가까운 놈 출력
def find_can_eat():
    need_dist = 0
    bfs_que = deque([[shark[0], shark[1]]])
    is_visited = [[False for __ in range(N)] for _ in range(N)]
    while len(bfs_que):
        can_eat_list = []
        # one round
        need_dist += 1
        for _ in range(len(bfs_que)):
            r, c = bfs_que.popleft()
            for i in range(4):
                next_r = r + dr[i]
                next_c = c + dc[i]
                if next_r < 0 or next_r >= N or next_c < 0 or next_c >= N or is_visited[next_r][next_c] or maps[next_r][next_c] > shark_size:
                    continue
                is_visited[next_r][next_c] = True
                # 상어보다 작으면 먹을 수 있는 리스트로 추가
                if 0 < maps[next_r][next_c] < shark_size:
                    can_eat_list.append((next_r, next_c))
                    continue
                # 먹을 수 없으면 지나감
                bfs_que.append((next_r, next_c))

        if len(can_eat_list) > 0:
            picked_fish = sorted(can_eat_list)[0]
            return picked_fish[0], picked_fish[1], need_dist

    return -1, -1, 0

# 상어 찾기
for r in range(N):
    for c in range(N):
        if maps[r][c] == SHARK:
            shark = [r, c]
            maps[r][c] = 0
            break

while True:
    dead_r, dead_c, need_dist = find_can_eat()
    if dead_c == -1 and dead_r == -1:
        break
    maps[dead_r][dead_c] = 0
    shark = [dead_r, dead_c]

    total_time += need_dist
    ate_num += 1
    if ate_num == shark_size:
        ate_num = 0
        shark_size += 1

print(total_time)



Search