[백준] 삼성 SW 역량 테스트 기출 문제 16326번 : 아기 상어 (파이썬/Python)
정답 코드 및 설명
정답 전체 코드
from collections import deque
def bfs(start, grid, size, n):
# 방향 벡터 설정 (상, 좌, 우, 하)
directions = [(-1, 0), (0, -1), (0, 1), (1, 0)]
# BFS를 위한 큐 초기화 및 시작점 등록
queue = deque([(start[0], start[1], 0)]) # (row, col, distance)
# 방문 체크 배열 초기화
visited = [[False] * n for _ in range(n)]
visited[start[0]][start[1]] = True
# 먹을 수 있는 물고기 리스트
eatable_fish = []
# BFS 실행
while queue:
r, c, dist = queue.popleft()
# 가능한 모든 방향으로 탐색
for dr, dc in directions:
nr, nc = r + dr, c + dc
if 0 <= nr < n and 0 <= nc < n and not visited[nr][nc]:
if grid[nr][nc] <= size: # 이동 가능 조건
visited[nr][nc] = True
if 0 < grid[nr][nc] < size: # 먹을 수 있는 물고기 조건
eatable_fish.append((dist + 1, nr, nc))
queue.append((nr, nc, dist + 1))
# 먹을 수 있는 가장 가까운 물고기 반환
if eatable_fish:
eatable_fish.sort()
return eatable_fish[0]
return None
n = int(input().strip())
grid = [list(map(int, input().split())) for _ in range(n)]
shark_size = 2 #초기 아기 상어 사이즈
eaten = 0 #먹은 물고기 수
time = 0 #총 지난 시간
#아기 상어 초기 위치 찾기
shark_pos = None
for i in range(n):
for j in range(n):
if grid[i][j] == 9:
shark_pos = (i,j)
grid[i][j] = 0 #상어 위치 초기화
break
if shark_pos:
break
while True: #먹을 수 있는 물고기가 없을 때 까지 반복
result = bfs(shark_pos, grid, shark_size, n)
if not result:
break
dist, fish_r, fish_c = result
# 물고기 먹기
grid[fish_r][fish_c] = 0
shark_pos = (fish_r, fish_c)
time += dist
eaten += 1
# 성장 조건 체크
if eaten == shark_size:
shark_size += 1
eaten = 0
print(time)문제 설명
NxN 크기의 격자에서 아기 상어가 물고기들과 함께 있다. 아기 상어는 초기 크기가 2이며, 이동하면서 자신보다 작은 크기의 물고기만 먹을 수 있다. 상어는 자신의 크기만큼 수의 물고리를 먹으면 크기가 1증가하고 크기가 같은 물고기는 먹지 못하지만 해당 칸을 지나갈 수 있다.
이 문제의 목표는 아기 상어가 더 이상 먹을 수 있는 물고기가 없을 때까지 걸리는 시간을 구하는 것이다.
이 문제를 풀기 위해선 아기 상어의 현재 위치에서 출발해서 먹을 수 있는 물고기들의 위치를 찾아가는 최단 경로를 계산해야한다. 각 칸을 방문하면서 아기 상어가 이동할 있는 지와 먹을 수 있는 물고기가 있는 지 확인한다.
코드 설명
n = int(input().strip())
grid = [list(map(int, input().split())) for _ in range(n)]
shark_size = 2 #초기 아기 상어 사이즈
eaten = 0 #먹은 물고기 수
time = 0 #총 지난 시간
#아기 상어 초기 위치 찾기
shark_pos = None
for i in range(n):
for j in range(n):
if grid[i][j] == 9:
shark_pos = (i,j)
grid[i][j] = 0 #상어 위치 초기화
break
if shark_pos:
break먼저 n 과 격자 데이터를 입력 받는다.
초기 사이즈, 먹은 물고기, 시간을 저장할 변수를 초기화 한다.
현재 입력 데이터로 바로 아기 상어 초기 위치를 알 수 없으니
9 가 있는 칸의 i,j 를 알아낸다.
def bfs(start, grid, size, n):
# 방향 벡터 설정 (상, 좌, 우, 하)
directions = [(-1, 0), (0, -1), (0, 1), (1, 0)]
# BFS를 위한 큐 초기화 및 시작점 등록
queue = deque([(start[0], start[1], 0)]) # (row, col, distance)
# 방문 체크 배열 초기화
visited = [[False] * n for _ in range(n)]
visited[start[0]][start[1]] = True
# 먹을 수 있는 물고기 리스트
eatable_fish = []
# BFS 실행
while queue:
r, c, dist = queue.popleft()
# 가능한 모든 방향으로 탐색
for dr, dc in directions:
nr, nc = r + dr, c + dc
if 0 <= nr < n and 0 <= nc < n and not visited[nr][nc]:
if grid[nr][nc] <= size: # 이동 가능 조건
visited[nr][nc] = True
if 0 < grid[nr][nc] < size: # 먹을 수 있는 물고기 조건
eatable_fish.append((dist + 1, nr, nc))
queue.append((nr, nc, dist + 1))
# 먹을 수 있는 가장 가까운 물고기 반환
if eatable_fish:
eatable_fish.sort()
return eatable_fish[0]
return None시작점을 기준으로 탐색을 실행한다. 각 칸에 대해서 상하좌우로 이동 가능한지 확인한다.
이동 가능한 칸 중에서 아기 상어가 먹을 수 있는 칸을 찾으면 그 위치와 이동에 필요한 거리를 저장한다.
먹을 수 있는 물고기 중 가장 가까운 것을 반환하고, 여러 마리 일 경우 가장 위에, 왼쪽에 있는 물고기를 선택한다.
while True: #먹을 수 있는 물고기가 없을 때 까지 반복
result = bfs(shark_pos, grid, shark_size, n)
if not result:
break
dist, fish_r, fish_c = result
# 물고기 먹기
grid[fish_r][fish_c] = 0
shark_pos = (fish_r, fish_c)
time += dist
eaten += 1
# 성장 조건 체크
if eaten == shark_size:
shark_size += 1
eaten = 0
먹을 수 있는 물고기가 없을 때까지 bfs 함수를 통해서 먹을 수 있는 물고기를 찾고 그 위치로 이동 시키고 물고기를 먹는다. 이때 아기 상어가 자신의 크기 만큼 물고기를 먹으면 크기를 증가 시킨다.
그 후 총 소요된 시간을 기록한다.
print(time)총 소요된 시간을 출력하면 정답이 된다.
