알고리즘 문제 풀이
125. [삼성기출21]Python 백준 16236 번 아기상어
코딩하는 덕구 🐶
2023. 6. 9. 16:14
728x90
안녕하세요 코딩하는 덕구입니다.
백준 16236 번 아기상어 입니다.
https://www.acmicpc.net/problem/16236
16236번: 아기 상어
N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가
www.acmicpc.net
먼저 백준 16236 번 아기상어 코드입니다. 설명은 아래에 있습니다.
from collections import deque
N = int(input())
board = [list(map(int, input().split())) for _ in range(N)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
candidate = []
def bfs(x, y):
visited = [[False for _ in range(N)] for _ in range(N)]
visited[x][y] = True
queue = deque()
queue.append([x, y, 0])
candidate = []
if board[x][y] == 9:
board[x][y] = 0
limit_time = 9999
while queue:
x, y, time = queue.popleft()
if time < limit_time:
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < N and 0 <= ny < N:
if not visited[nx][ny]:
if board[nx][ny] == 0 or board[nx][ny] == shark_size:
visited[nx][ny] = True
queue.append([nx, ny, time + 1])
elif board[nx][ny] < shark_size:
visited[nx][ny] = True
candidate.append([nx, ny, time + 1])
limit_time = time + 1
return candidate
exp = 0
total_time = 0
shark_size = 2
for i in range(N):
for j in range(N):
if board[i][j] == 9:
x = i
y = j
while True:
candidate = bfs(x, y)
if len(candidate) == 0:
break
candidate.sort(key=lambda x : (x[0], x[1])) #조건에 맞는 순서로 정렬
x, y, time = candidate[0]#맨앞 후보 잡아먹기
board[x][y] = 9
exp += 1
if exp == shark_size: #상어 성장
shark_size += 1
exp = 0
total_time += time
print(total_time)문제 접근
1. bfs를 통해 가까운 거리의 먹을 수 있는 물고기를 탐색합니다.
2. 조건에 맞는 물고기를 먹고 그 자리에서 다시 bfs를 반복합니다.
Python 코드 구현
bfs에 필요한 변수들을 선언합니다.
from collections import deque
N = int(input())
board = [list(map(int, input().split())) for _ in range(N)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
candidate = []
맨 처음 상어의 위치를 찾고, 해당 위치부터 bfs를 실행합니다.
bfs는 가까운 먹이감들의 좌표, 거리를 담는 리스트를 return합니다.
bfs 실행 후 먹이를 먹는 순서로 리스트를 정렬하고, 먹이를 먹습니다.
또한 성장조건이 된다면 상어는 성장합니다.
먹을 수 있는 물고기가 없을때 까지 반복하고 답을 출력하면 됩니다.
exp = 0
total_time = 0
shark_size = 2
for i in range(N):
for j in range(N):
if board[i][j] == 9:
x = i
y = j
while True:
candidate = bfs(x, y)
if len(candidate) == 0:
break
candidate.sort(key=lambda x : (x[0], x[1])) #조건에 맞는 순서로 정렬
x, y, time = candidate[0]#맨앞 후보 잡아먹기
board[x][y] = 9
exp += 1
if exp == shark_size: #상어 성장
shark_size += 1
exp = 0
total_time += time
print(total_time)
bfs는 두가지 조건이 있습니다.
먹을 수 있는가, 없는가
만약 먹을 수 있다면 후보 리스트에 추가합니다.
먹을 수 없고, 지나갈 수 있다면 해당 위치에서 다시 탐색합니다.
이때 후보 리스트에 있는 먹있감보다 거리가 멀어지면 탐색하지 않습니다.
def bfs(x, y):
visited = [[False for _ in range(N)] for _ in range(N)]
visited[x][y] = True
queue = deque()
queue.append([x, y, 0])
candidate = []
if board[x][y] == 9:
board[x][y] = 0
limit_time = 9999
while queue:
x, y, time = queue.popleft()
if time < limit_time:
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < N and 0 <= ny < N:
if not visited[nx][ny]:
if board[nx][ny] == 0 or board[nx][ny] == shark_size:
visited[nx][ny] = True
queue.append([nx, ny, time + 1])
elif board[nx][ny] < shark_size:
visited[nx][ny] = True
candidate.append([nx, ny, time + 1])
limit_time = time + 1
return candidate
파이썬 백준 16236 번 아기상어 최종 코드입니다.
from collections import deque
N = int(input())
board = [list(map(int, input().split())) for _ in range(N)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
candidate = []
def bfs(x, y):
visited = [[False for _ in range(N)] for _ in range(N)]
visited[x][y] = True
queue = deque()
queue.append([x, y, 0])
candidate = []
if board[x][y] == 9:
board[x][y] = 0
limit_time = 9999
while queue:
x, y, time = queue.popleft()
if time < limit_time:
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < N and 0 <= ny < N:
if not visited[nx][ny]:
if board[nx][ny] == 0 or board[nx][ny] == shark_size:
visited[nx][ny] = True
queue.append([nx, ny, time + 1])
elif board[nx][ny] < shark_size:
visited[nx][ny] = True
candidate.append([nx, ny, time + 1])
limit_time = time + 1
return candidate
exp = 0
total_time = 0
shark_size = 2
for i in range(N):
for j in range(N):
if board[i][j] == 9:
x = i
y = j
while True:
candidate = bfs(x, y)
if len(candidate) == 0:
break
candidate.sort(key=lambda x : (x[0], x[1])) #조건에 맞는 순서로 정렬
x, y, time = candidate[0]#맨앞 후보 잡아먹기
board[x][y] = 9
exp += 1
if exp == shark_size: #상어 성장
shark_size += 1
exp = 0
total_time += time
print(total_time)
백준 16236 번 아기상어 Python 코드였습니다.
감사합니다.
728x90