[ Contents ]
1. 문제 (링크 참조)
2. 문제 풀이
아기 상어가 먹을 수 있는 먹잇감을 모두 먹는 데에 걸리는 시간을 구하는 문제입니다. 자신보다 작은 물고기만 먹을 수 있고, 크기 2부터 시작합니다. 자신보다 큰 물고기는 통과할 수 없으며, 자신과 동일한 크기면 통과할 수 있습니다.
2022.02.23 - [Algorithm] - [Algorithm] 너비 우선 탐색(BFS), 가까운 주변부터 찾자
BFS탐색을 이용해서 '현재 위치'에서 자신이 먹을 수 있는 물고기를 탐색합니다. 동일한 거리에 있을 경우에는 '위', '왼쪽'에 있는 물고기를 먼저 먹습니다.
3. 코드
from collections import deque
import sys
input = sys.stdin.readline
#입력
N = int(input())
sea = [] # 그래프
startX, startY = 0, 0 # 아기상어 위치
for i in range(N):
lst = list(map(int, input().split()))
for j in range(N):
if lst[j] == 9:
lst[j] = 0 # 크기가 9인 물고기로 오인하지 않도록
startX, startY = i, j # 아기상어 위치
sea.append(lst)
물고기 위치를 입력받고, 아기 상어의 위치를 저장합니다. 아기 상어의 위치는 9로 입력되며, 크기가 9인 물고기로 오인하지 않도록 0으로 바꿔줍니다.
# BFS탐색
direction = [(0, 1), (-1, 0), (0, -1), (1, 0)] # 상하좌우
size = 2
move = 0
eat = 0
while True:
visited = [[False] * N for _ in range(N)] # 방문표시
queue = deque([(startX, startY, 0)]) # 시작 위치
visited[startX][startY] = True
flag = 9999 # 먹을 수 있는 물고기 탐색여부
fish = [] # 물고기 위치
while queue:
x, y, cnt = queue.popleft()
if cnt > flag:
break
#상하좌우 탐색
for dx, dy in direction:
nx, ny = x+dx, y+dy
# 범위를 벗어나지 않고, 자신이 지나갈 수 있는 미방문인 곳을 탐색
if 0 <= nx < N and 0 <= ny < N and sea[nx][ny] <= size and not visited[nx][ny]:
visited[nx][ny] = True # 방문
queue.append((nx, ny, cnt+1))
# 자신보다 작은 물고기가 있으면 먹음
if 0 < sea[nx][ny] < size:
fish.append((nx, ny, cnt+1))
flag = cnt # 탐색완료
아기 상어 위치에서 가장 가까운 먹잇감 위치를 BFS 탐색합니다. 자신보다 작은 먹잇감을 찾았으면, queue에 넣고 해당 위치에서 다시 BFS 탐색할 준비를 합니다.
# 먹을 수 있는 물고기가 있으면 계속 탐색
if fish:
fish.sort() #위, 왼쪽 물고기 먼저 먹음
x, y, dist = fish[0] #먹을 물고기 위치와 필요한 이동거리
sea[x][y] = 0 #먹고나면 빈 칸
move += dist
# 먹은 물고기 횟수+1, 사이즈와 동일하다면 사이즈업
eat += 1
if eat == size:
size += 1
eat = 0
startX, startY = x, y
# 더이상 먹을 수 있는 물고기 없음
else:
break
print(move)
print(move)를 제외하곤 while True 반복문 안입니다. BFS탐색에서 찾은 물고기 중 거리가 가장 짧은 물고기를 먹습니다. 거리가 같다면 가장 위, 왼쪽인 물고기를 먼저 먹습니다. (거리, 행, 열 순으로 오름차순 정렬)
먹고 난 물고기칸은 빈 칸(0)이 되고, 해당 거리만큼 시간을 더해줍니다. (1초에 1칸 이동) 먹은 물고기 횟수를 +1 해주고, 사이즈와 동일해졌다면 사이즈를 올려줍니다. 이후 시작 지점을 먹은 물고기 칸(x, y)으로 갱신하고 BFS 탐색을 진행합니다.
만약 더 이상 먹을 수 있는 물고기가 없다면 탐색을 종료합니다.
cf) Flag 오류
from collections import deque
import sys
input = sys.stdin.readline
#입력
N = int(input())
sea = [] # 그래프
startX, startY = 0, 0 # 아기상어 위치
for i in range(N):
lst = list(map(int, input().split()))
for j in range(N):
if lst[j] == 9:
lst[j] = 0 # 크기가 9인 물고기로 오인하지 않도록
startX, startY = i, j # 아기상어 위치
sea.append(lst)
# BFS탐색
direction = [(0, 1), (-1, 0), (0, -1), (1, 0)] # 상하좌우
size = 2
move = 0
eat = 0
while True:
visited = [[False] * N for _ in range(N)] # 방문표시
queue = deque([(startX, startY, 0)]) # 시작 위치
visited[startX][startY] = True
flag = False # 먹을 수 있는 물고기 탐색여부
fish = [] # 물고기 위치
while queue:
x, y, cnt = queue.popleft()
if flag:
break
#상하좌우 탐색
for dx, dy in direction:
nx, ny = x+dx, y+dy
# 범위를 벗어나지 않고, 자신이 지나갈 수 있는 미방문인 곳을 탐색
if 0 <= nx < N and 0 <= ny < N and sea[nx][ny] <= size and not visited[nx][ny]:
visited[nx][ny] = True # 방문
queue.append((nx, ny, cnt+1))
# 자신보다 작은 물고기가 있으면 먹음
if 0 < sea[nx][ny] < size:
fish.append((nx, ny, cnt+1))
flag = True # 탐색완료
# 먹을 수 있는 물고기가 있으면 계속 탐색
if fish:
fish.sort() #위, 왼쪽 물고기 먼저 먹음
x, y, dist = fish[0] #먹을 물고기 위치와 필요한 이동거리
sea[x][y] = 0 #먹고나면 빈 칸
move += dist
# 먹은 물고기 횟수+1, 사이즈와 동일하다면 사이즈업
eat += 1
if eat == size:
size += 1
eat = 0
startX, startY = x, y
# 더이상 먹을 수 있는 물고기 없음
else:
break
print(move)
위 정답코드와 달리, flag를 bool 변수로 두었습니다. break 조건을 cnt > flag로 두지 않으면, 거리가 같은 다른 물고기를 탐색하지 못합니다.
5
3 3 2 4 3
1 4 5 3 1
1 4 3 3 2
4 3 2 3 1
3 3 1 3 9
정답: 31
출력: 34
위 예제를 살펴보면 12초에서 잘못된 선택을 합니다.
본래라면 상단이고 왼쪽인 물고리를 먹어야 합니다. (아기 상어의 위치를 9로 표시)
하지만, 위 코드는 12초에서 오른쪽 상단의 물고기를 먹습니다. (먹은 물고기 자리를 -1로 표시)
먹잇감만 찾으면, 1~3번의 탐색 뒤에 발견될 동일한 거리의 먹잇감이 무시되기 때문입니다. 따라서 cnt > flag로 동일 거리의 먹잇감 탐색이 이루어지도록 조정하면, 정답 코드가 됩니다.
'Algorithm' 카테고리의 다른 글
[구현/해시] 백준 1076 저항 - 파이썬(Python) (0) | 2022.03.26 |
---|---|
[구현/수학] 백준 2003 수들의 합 2 - 파이썬(Python) (0) | 2022.03.25 |
[구현/수학] 백준 2167 2차원 배열의 합 - 파이썬(Python) (0) | 2022.03.23 |
[자료구조/큐] 백준 18258 큐 2 - 파이썬(Python) (0) | 2022.03.22 |
[Algorithm] 다익스트라(Dijkstra), 지름길의 지름길로 찾는 최적경로 (0) | 2022.03.22 |
댓글