[BOJ 16236] 아기 상어 (Python)
문제
복습 요망!
풀이
쉽지 않은 문제였다. 전부터 시뮬레이션, 구현 문제에 어려움을 느꼈는데, 극복 and 정복하도록 더 열심히 해야겠다...
시뮬레이션 문제는 주어진 조건과 진행방식을 따라서 차근차근 구현하면 된다. 조건과 탐색을 진행하는 코드의 순서와 방식이 중요하다고 생각한다.
-
아기 상어의 시작점을 구하고 큐에 넣는다.
-
현재 아기 상어의 위치에서 최단거리를 구하는 테이블을 생선한다.
-
생성된 거리테이블과 물고기 크기테이블을 통해 최단거리에 있고 먹을 수 있는 물고기를 찾아 먹은 후 걸린 시간을 계산한다.
-
먹을 물고기가 없거나 존재하지 않을 때까지 위 과정을 반복한다.
코드
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
Author And Source
이 문제에 관하여([BOJ 16236] 아기 상어 (Python)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@kimdukbae/BOJ-16236-아기-상어-Python
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
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
Author And Source
이 문제에 관하여([BOJ 16236] 아기 상어 (Python)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@kimdukbae/BOJ-16236-아기-상어-Python저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)