728x90
문제
https://www.acmicpc.net/problem/16236
풀이
BFS(너비 우선 탐색)를 사용해 풀었습니다.
- 아기 상어의 위치(
baby_shark
)를 찾아 해당 위치의 값을 0으로 바꾸고 위치를 저장합니다. BFS
함수 내의fish
리스트에는 같은 거리 상에 있는 먹을 물고기들을 저장합니다.- 상하좌우를 확인하며 0 혹은 같은 크기의 물고기는 지나가고, 아기 상어보다 작은 물고기를
fish
리스트에 추가합니다. - 만약 먹을 수 있는 물고기가 있다면 물고기를 맨 위쪽, 왼쪽 순으로 정렬해 그 중 첫 번째 물고기를 선택합니다.
- 총 시간(
time
)에 걸린 시간(t
)을 추가합니다. - 그러나, 공간에 더 이상 먹을 수 있는 물고기가 없다면 총 시간(
time
)을 출력하고 마칩니다.
코드
파이썬
import sys
from collections import deque
input = sys.stdin.readline
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
N = int(input())
graph = [list(map(int, input().split())) for _ in range(N)]
def getStart():
for i in range(N):
for j in range(N):
if graph[i][j] == 9:
graph[i][j] = 0
return (i, j)
def BFS(x, y):
fish = []
L = 0
queue = deque()
visited = [[False] * N for _ in range(N)]
visited[x][y] = True
queue.append((x, y))
while queue:
for _ in range(len(queue)):
x, y = queue.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < N and 0 <= ny < N and not visited[nx][ny]:
if graph[nx][ny] == 0 or graph[nx][ny] == size:
visited[nx][ny] = True
queue.append((nx, ny))
elif graph[nx][ny] < size:
visited[nx][ny] = True
fish.append((nx, ny))
L += 1
if fish:
fish.sort()
graph[fish[0][0]][fish[0][1]] = 0
return [fish[0], L]
return [[], 0]
time = 0
baby_shark = getStart()
size = 2
eaten = 0
while True:
baby_shark, t = BFS(baby_shark[0], baby_shark[1])
if t == 0:
print(time)
break
else:
time += t
eaten += 1
if size == eaten:
size += 1
eaten = 0
728x90
'🚩 코딩테스트 > 알고리즘' 카테고리의 다른 글
[백준] 5052번: 전화번호 목록 (0) | 2023.05.29 |
---|---|
[백준] 1967번: 트리의 지름 (1) | 2023.05.15 |
[백준] 2206번: 벽 부수고 이동하기 (0) | 2023.05.11 |
[백준] 1987번: 알파벳 (0) | 2023.05.11 |
[백준] 7569번: 토마토 (0) | 2023.05.11 |
728x90
문제
https://www.acmicpc.net/problem/16236
풀이
BFS(너비 우선 탐색)를 사용해 풀었습니다.
- 아기 상어의 위치(
baby_shark
)를 찾아 해당 위치의 값을 0으로 바꾸고 위치를 저장합니다. BFS
함수 내의fish
리스트에는 같은 거리 상에 있는 먹을 물고기들을 저장합니다.- 상하좌우를 확인하며 0 혹은 같은 크기의 물고기는 지나가고, 아기 상어보다 작은 물고기를
fish
리스트에 추가합니다. - 만약 먹을 수 있는 물고기가 있다면 물고기를 맨 위쪽, 왼쪽 순으로 정렬해 그 중 첫 번째 물고기를 선택합니다.
- 총 시간(
time
)에 걸린 시간(t
)을 추가합니다. - 그러나, 공간에 더 이상 먹을 수 있는 물고기가 없다면 총 시간(
time
)을 출력하고 마칩니다.
코드
파이썬
import sys
from collections import deque
input = sys.stdin.readline
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
N = int(input())
graph = [list(map(int, input().split())) for _ in range(N)]
def getStart():
for i in range(N):
for j in range(N):
if graph[i][j] == 9:
graph[i][j] = 0
return (i, j)
def BFS(x, y):
fish = []
L = 0
queue = deque()
visited = [[False] * N for _ in range(N)]
visited[x][y] = True
queue.append((x, y))
while queue:
for _ in range(len(queue)):
x, y = queue.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < N and 0 <= ny < N and not visited[nx][ny]:
if graph[nx][ny] == 0 or graph[nx][ny] == size:
visited[nx][ny] = True
queue.append((nx, ny))
elif graph[nx][ny] < size:
visited[nx][ny] = True
fish.append((nx, ny))
L += 1
if fish:
fish.sort()
graph[fish[0][0]][fish[0][1]] = 0
return [fish[0], L]
return [[], 0]
time = 0
baby_shark = getStart()
size = 2
eaten = 0
while True:
baby_shark, t = BFS(baby_shark[0], baby_shark[1])
if t == 0:
print(time)
break
else:
time += t
eaten += 1
if size == eaten:
size += 1
eaten = 0
728x90
'🚩 코딩테스트 > 알고리즘' 카테고리의 다른 글
[백준] 5052번: 전화번호 목록 (0) | 2023.05.29 |
---|---|
[백준] 1967번: 트리의 지름 (1) | 2023.05.15 |
[백준] 2206번: 벽 부수고 이동하기 (0) | 2023.05.11 |
[백준] 1987번: 알파벳 (0) | 2023.05.11 |
[백준] 7569번: 토마토 (0) | 2023.05.11 |