[백준] 16236. 아기상어 (python / 파이썬)
1. 입력
첫째 줄에 공간의 크기 N(2 ≤ N ≤ 20)이 주어진다.
둘째 줄부터 N개의 줄에 공간의 상태가 주어진다
4
4 3 2 1
0 0 0 0
0 0 9 0
1 2 3 4
0 : 빈 공간
1 ~ 6 : 물고기가 위치해 있으며, 위치한 물고기의 크기
9 : 상어의 위치
2. 출력
상어가 이동한 거리를 출력한다.
14
- 문제에선 시간을 출력하라 하지만, 1초에 1단위거리를 이동하기 때문에 편의상 거리로 치환한다.
3. 풀이
본 문제는 간단히 말해 상어로부터 가장 가까운 먹을 수 있는 물고기를 먹는 문제이다. 즉, 최단거리를 찾는 알고리즘을 요구하고 있기 때문에 BFS로 구현이 가능하다.
다만, 단순히 BFS로 구현하기에는 신경써야 할 조건이 있다.
- 상어의 크기보다 작은 물고기만 먹을 수 있다.
- 상어의 크기보다 큰 물고기는 지나갈 수 없다.
- 상어는 본인의 크기만큼의 물고기를 먹었을 때 크기가 1 커진다.
- 가령, 크기가 2라면 물고기 두 마리를 먹어야 크기가 3이 된다.
즉, 상어의 크기가 BFS에서 큰 역할을 하는 변수가 된다. 이를 고려하여 문제 풀이를 진행하였다.
3.1. Class Shark
문제를 풀기 위해 상어의 정보를 저장할 Shark
클래스를 생성하였다.
해당 클래스는 __init__()
, is_reachable()
, eat_a_fish()
세 가지의 메소드로 구성된다.
3.1.1 __init__()
def __init__(self, shark, mat):
self.shark_loc = shark["cur_loc"]
self.size = shark['size']
self.mat = mat
self.exp = 0
self.shark_loc
은 현재 상어의 위치를 나타낸다. 이는 (row, column)
형태의 tuple이다.
self.size
는 현재 상어의 크기를 정수로 의미한다.
self.mat
는 수족관의 공간을 정수 행렬로 표현한 것이다.
self.exp
는 상어가 먹은 물고기의 마리수이다.
3.1.2. is_reachable()
메소드 이름만 볼 때에는 boolean
값을 출력으로 할 것 같으나, 상어가 먹을 수 있는 물고기의 배열을 출력한다. 처음엔 boolean
값을 출력하였으나, 시간 초과 문제로 수정하였다.
3.1.2.1 Temporary matrix
mat = [row.copy() for row in self.mat]
mat[self.shark_loc[0]][self.shark_loc[1]] = -1
BFS를 사용할 때 중요한 것은 "이미 방문한 공간을 재방문하지 않는 것""이다. 따라서 이를 위해 별도의 임시 행렬을 구현해 주었다. 만약 방문이 이루어졌다면 방문한 공간은 -1
로 변경된다.
제일 먼저 상어가 있던 공간은 탐색할 필요가 없으니 -1
로 초기화해준다.
self.mat.copy()
만으로는 행렬이 복사되지 않는다. 따라서 행렬을 복사할 때에는 행렬 내의row
에 관해 일일이copy()
를 수행해주어야 한다.
3.1.2.2 BFS
directions = [(-1,0), (1,0), (0,-1), (0,1)] # 움직일 수 있는 방향
queue = deque([(0, self.shark_loc)])
available_fishes = []
while queue:
level, (row, col) = queue.popleft()
for direction in directions:
d_row, d_col = direction
new_row = row + d_row
new_col = col + d_col
# 유효성 검사 (segmentation error 방지)
if 0 <= new_row < shape and 0 <= new_col < shape:
# 이동할 수 있을 시에 추가
if 0 <= mat[new_row][new_col] <= self.size:
queue.append((level +1, (new_row, new_col)))
if 0 < mat[new_row][new_col] < self.size:
available_fishes.append((level+1, (new_row, new_col)))
mat[new_row][new_col] = -1
return None
directions
는 상어가 움직일 수 있는 방향을 의미한다. 예를 들어 (-1,0)
은 상어가 위 방향으로 움직이는 것을 뜻한다.
queue
는 상어가 이동할 수 있는 공간을 저장할 큐이다. 0
은 상어가 이동한 거리를 의미한다.
available_fishes
는 상어가 먹을 수 있는 물고기를 저장할 공간이다.
만약 상어가 이동할 수 있다면, direction
의 값을 통해 상어가 더 이동할 수 있는지 파악한다.
- 만약 상어의 위치가
(0,0)
이라면 왼쪽이나 위로는 이동할 수 없기 때문에, 이동할 수 없을 때의 경우 역시 고려한다. - 만약 상어가 이동하려는 곳에 상어보다 더 큰 물고기가 있다면 이동할 수 없기 때문에 이 역시 고려한다.
- 만약 상어가 이동하려는 곳이 이미 방문한 곳이라면 방문할 필요가 없기 때문에 이 역시 고려한다.
상어가 더 이동할 수 있다면 이동 가능한 공간의 정보를 queue
에 추가한다.
상어가 이동할 수 있는 공간의 고기를 먹을 수 있다면 공간의 정보를 available_fishes
에도 추가한다.
만약 물고기가 잡혔다면, 더 이상 탐색을 진행할 필요가 없다. 이를 위해 while loop 탈출 조건을 추가해준다.
current_level = 0
if level != current_level:
if available_fishes:
return available_fishes
else:
current_level = level
level
은 root node로부터 해당 node까지의 거리라고 가정하자.
만약 queue
에서 새로운 node를 가져왔는데, 이전에 가져온 node의 level
과 다르다면 이전 노드의 형제 노드에 대한 탐색은 전부 끝나고 새로운 자식 노드를 탐색하고 있다고 할 수 있다.
따라서 형제 노드에 대한 탐색이 끝났을 때, available_fish
값을 확인하여 추가적인 탐색을 막는다.
최종적인 is_reachable()
메소드의 형태는 다음과 같다.
def is_reachable(self):
# level이 올라갈 때마다 가능한 물고기가 잡혔는지 check
mat = [row.copy() for row in self.mat]
mat[self.shark_loc[0]][self.shark_loc[1]] = -1 # 처음 상어 위치 마킹
directions = [(-1,0), (1,0), (0,-1), (0,1)] # 움직일 수 있는 방향
current_level = 0
queue = deque([(current_level, self.shark_loc)])
available_fishes = []
while queue:
level, (row, col) = queue.popleft()
# level이 올라갈 때마다 check
if level != current_level:
if available_fishes:
return available_fishes
else:
current_level = level
for direction in directions:
d_row, d_col = direction
new_row = row + d_row
new_col = col + d_col
# 유효성 검사 (segmentation error 방지)
if 0 <= new_row < shape and 0 <= new_col < shape:
# 이동할 수 있을 시에 추가
if 0 <= mat[new_row][new_col] <= self.size:
queue.append((level +1, (new_row, new_col)))
if 0 < mat[new_row][new_col] < self.size:
available_fishes.append((level+1, (new_row, new_col)))
mat[new_row][new_col] = -1
return None
3.1.3. eat_a_fish()
이는 상어가 물고기를 먹었을 때 변경될 사항을 정리한 메소드이다.
def eat_a_fish(self, loc):
self.mat[self.shark_loc[0]][self.shark_loc[1]] = 0
self.shark_loc = loc # 위치 갱신
self.exp += 1 # 경험치 증가
if self.exp == self.size:
self.size += 1
self.exp = 0
self.mat[loc[0]][loc[1]] = 9
loc
은 먹을 수 있는 물고기가 위치한 장소를 의미한다.
상어가 물고기를 먹으려고 이동하기 때문에 원래 상어가 있던 공간은 0으로 바꿔주고, 상어의 좌표를 물고기의 좌표로 바꿔준다.
- 앞서 이미 방문한 공간은
-1
로 하기로 했는데 왜0
으로 했는지 의문이 들 수 있다.self.mat
는 원본이고,-1
는list.copy()
를 통해 복사한 복사본에 저장하였다. 만약 원본에-1
을 저장한다면 탐색이 불가능한 지역이 되기 때문에 이후 탐색에 영향을 미칠 수 있다.
그리고 상어가 먹은 물고기의 수를 1
증가시킨다. 만약 물고기의 수가 상어의 크기와 같다면, 상어의 크기를 1
증가시키고, 물고기의 수를 0
으로 초기화해준다.
3.2. Run
이제 Shark
클래스를 정의했으므로 문제를 풀어보자.
shark = Shark(shark, mat)
time = 0
while True:
fish_list = shark.is_reachable()
if fish_list:
fish_list.sort()
#print(fish_list)
time += fish_list[0][0]
shark.eat_a_fish(fish_list[0][1])
else:
break
print(time)
is_reachable
은 상어가 먹을 수 있는 물고기의 배열을 반환한다. 만약 먹을 수 있는 물고기가 없다면 그대로 while loop를 탈출하면 된다.
그러나 먹을 수 있는 고기가 있다면 해당 배열을 sort
를 통해 정렬한다. 배열은 (물고기까지의 거리, (row_index, column_index))
의 형태로 표현되어 있기 때문에 그냥 sort
를 하더라도 문제의 조건 (거리가 같다면 row가 낮은 것 먼저, row가 같다면 column이 낮은 것 먼저)을 만족한다.
그리고 첫 번째 값(거리가 가장 작은 물고기)을 통해 시간을 늘려주고, 상어에게 물고기를 먹이는 것을 반복한다.
4. 전체 코드
import sys
from collections import deque
input = sys.stdin.readline
# get input
shape = int(input())
mat = [list(map(int, input().split())) for _ in range(shape)]
# check locations of shark and fishes
shark = {"cur_loc" : [], "size" : 2} # info shark
for row_idx, row in enumerate(mat):
for ele_idx, ele in enumerate(row):
if ele == 9:
shark["cur_loc"] = (row_idx, ele_idx)
class Shark():
def __init__(self, shark, mat):
self.shark_loc = shark["cur_loc"]
self.size = shark['size']
self.mat = mat
self.exp = 0
def is_reachable(self):
# level이 올라갈 때마다 가능한 물고기가 잡혔는지 check
mat = [row.copy() for row in self.mat]
mat[self.shark_loc[0]][self.shark_loc[1]] = -1 # 처음 상어 위치 마킹
directions = [(-1,0), (1,0), (0,-1), (0,1)] # 움직일 수 있는 방향
current_level = 0
queue = deque([(current_level, self.shark_loc)])
available_fishes = []
while queue:
level, (row, col) = queue.popleft()
# level이 올라갈 때마다 check
if level != current_level:
if available_fishes:
return available_fishes
else:
current_level = level
for direction in directions:
d_row, d_col = direction
new_row = row + d_row
new_col = col + d_col
# 유효성 검사 (segmentation error 방지)
if 0 <= new_row < shape and 0 <= new_col < shape:
# 이동할 수 있을 시에 추가
if 0 <= mat[new_row][new_col] <= self.size:
queue.append((level +1, (new_row, new_col)))
if 0 < mat[new_row][new_col] < self.size:
available_fishes.append((level+1, (new_row, new_col)))
mat[new_row][new_col] = -1
return None
def eat_a_fish(self, loc):
self.mat[self.shark_loc[0]][self.shark_loc[1]] = 0
self.shark_loc = loc # 위치 갱신
self.exp += 1 # 경험치 증가
if self.exp == self.size:
self.size += 1
self.exp = 0
self.mat[loc[0]][loc[1]] = 9
# run
shark = Shark(shark, mat)
time = 0
while True:
fish_list = shark.is_reachable()
if fish_list:
fish_list.sort()
#print(fish_list)
time += fish_list[0][0]
shark.eat_a_fish(fish_list[0][1])
else:
break
print(time)
4.1. 비고 (실패사례)
import sys
from collections import deque
input = sys.stdin.readline
# get input
shape = int(input())
mat = [list(map(int, input().split())) for _ in range(shape)]
# check locations of shark and fishes
shark = {"cur_loc" : [], "size" : 2} # info shark
for row_idx, row in enumerate(mat):
for ele_idx, ele in enumerate(row):
if ele == 9:
shark["cur_loc"] = (row_idx, ele_idx)
class Shark():
def __init__(self, shark, mat):
self.shark_loc = shark["cur_loc"]
self.size = shark['size']
self.mat = mat
self.exp = 0
def is_reachable(self):
# level이 올라갈 때마다 가능한 물고기가 잡혔는지 check
mat = [row.copy() for row in self.mat]
mat[self.shark_loc[0]][self.shark_loc[1]] = -1 # 처음 상어 위치 마킹
directions = [(-1,0), (1,0), (0,-1), (0,1)] # 움직일 수 있는 방향
current_level = 0
queue = deque([(current_level, self.shark_loc)])
available_fishes = []
while queue:
level, (row, col) = queue.popleft()
# level이 올라갈 때마다 check
if level != current_level:
if available_fishes:
return available_fishes
else:
current_level = level
for direction in directions:
d_row, d_col = direction
new_row = row + d_row
new_col = col + d_col
# 유효성 검사 (segmentation error 방지)
if 0 <= new_row < shape and 0 <= new_col < shape:
# 이동할 수 있을 시에 추가
if 0 <= mat[new_row][new_col] <= self.size:
queue.append((level +1, (new_row, new_col)))
if 0 < mat[new_row][new_col] < self.size:
available_fishes.append((level+1, (new_row, new_col)))
mat[new_row][new_col] = -1
return None
def eat_a_fish(self, loc):
self.mat[self.shark_loc[0]][self.shark_loc[1]] = 0
self.shark_loc = loc # 위치 갱신
self.exp += 1 # 경험치 증가
if self.exp == self.size:
self.size += 1
self.exp = 0
self.mat[loc[0]][loc[1]] = 9
# run
shark = Shark(shark, mat)
time = 0
while True:
fish_list = shark.is_reachable()
if fish_list:
fish_list.sort()
#print(fish_list)
time += fish_list[0][0]
shark.eat_a_fish(fish_list[0][1])
else:
break
print(time)
처음에는 먹을 수 있는 물고기를 추린 후에, 각각의 물고기에 대해 거리를 측정하였다. 그러나 이런 식으로 한다면 물고기 한 마리마다 BFS와 의 행렬 초기화가 반복되기 때문에 시간이 굉장히 오래 걸린다.
따라서 각각의 물고기에 대해 길을 찾는 것 대신에 모든 물고기에 대해 한 번의 길을 찾고, 먹을 수 있는 물고기를 찾았을 때 길찾기를 종료하는 것으로 바꿔 문제를 풀었다.
4.1.1 실패 코드
import sys
from collections import deque
input = sys.stdin.readline
# get input
shape = int(input())
mat = [list(map(int, input().split())) for _ in range(shape)]
# check locations of shark and fishes O(n^2)
shark = {"cur_loc" : [], "size" : 2} # info shark
fish_locs = {} # key : fish_size, value : fish_location
for row_idx, row in enumerate(mat):
for ele_idx, ele in enumerate(row):
if 0 < ele < 9:
fish_size = ele
if fish_size not in fish_locs.keys():
fish_locs[fish_size] = []
fish_locs[fish_size].append((row_idx, ele_idx))
elif ele == 9:
shark["cur_loc"] = (row_idx, ele_idx)
#print(fish_locs)
#print(shark)
"""
어떻게 풀 것인가?
목표 : 먹을 수 있는 물고기를 찾는다
1. 크기가 상어보다 작은 물고기들을 찾는다.
2. 그 중 거리가 가장 가까운 놈을 먹는다
- 거리가 다 가깝다면 제일 위 (1), 제일 왼쪽 (2)
반복
"""
class Shark():
def __init__(self, shark, fish_loc, mat):
self.shark_loc = shark["cur_loc"]
self.size = shark['size']
self.fish_locs = fish_loc
self.eatable_fishes = []
if self.fish_locs:
self.eatable_fishes = self.fish_locs[1] # 크기가 상어보다 작은 물고기들 목록
self.mat = mat
self.exp = 0
def _is_reachable(self, fish_loc):
# 한 물고기를 잡을 수 있는지
mat = [row.copy() for row in self.mat]
directions = [(-1,0), (1,0), (0,-1), (0,1)] # 움직일 수 있는 방향
start = self.shark_loc
queue = deque([(0,start)])
while queue:
level, (row, col) = queue.popleft()
mat[row][col] = -1 # 중복 검색을 막기 위해
for direction in directions:
d_row, d_col = direction
new_row = row + d_row
new_col = col + d_col
new_loc = (new_row, new_col)
if new_loc == fish_loc:
return level+1
# 유효성 검사
if 0 <= new_row < shape and 0 <= new_col < shape:
# 갈 수 있을 시에 추가
if 0 <= mat[new_row][new_col] <= self.size:
queue.append((level +1, (new_row, new_col)))
#print(queue)
return shape*2
def are_reachable(self):
closest = shape**2
loc_to_eat = (shape, shape)
for fish_loc in self.eatable_fishes:
dist = self._is_reachable(fish_loc)
if dist < closest:
closest = dist
loc_to_eat = fish_loc
elif dist == closest:
if loc_to_eat[0] > fish_loc[0]: # 새로운 좌표의 low가 더 낮다면 (loc 0,3 fish 3,0)
loc_to_eat = fish_loc
elif loc_to_eat[0] == fish_loc[0] and loc_to_eat[1] > fish_loc[1]: # 새로운 좌표의 column이 더 왼쪽이라면
loc_to_eat = fish_loc
return closest, loc_to_eat
def eat_a_fish(self, loc):
self.eatable_fishes.remove(loc) # 물고기 제거
self.mat[self.shark_loc[0]][self.shark_loc[1]] = 0
self.shark_loc = loc # 위치 갱신
self.exp += 1 # 경험치 증가
if self.exp == self.size:
self.size += 1
if self.size-1 in fish_locs.keys():
self.eatable_fishes += fish_locs[self.size-1] # 물고기 갱신
self.exp = 0
self.mat[loc[0]][loc[1]] = 9
# run
shark = Shark(shark, fish_locs, mat)
time = 0
while shark.eatable_fishes:
# 가장 가까운 먹이를 찾음
closest, loc = shark.are_reachble()
shark.eat_a_fish(loc)
time += closest
print(time)
Author And Source
이 문제에 관하여([백준] 16236. 아기상어 (python / 파이썬)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@veonico/백준-16236.-아기상어-python-파이썬저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)