<div id="readability-page-1" class="page"><div><a href="https://www.acmicpc.net/problem/16236">https://www.acmicpc.net/problem/16236</a>
BOJ 16236 아기상어 문제를 풀어봤습니다.
<h2 id="문제파악"><a href="#%EB%AC%B8%EC%A0%9C%ED%8C%8C%EC%95%85" aria-label="문제파악 permalink"></a>문제파악</h2>
구현문제들은 역시 문제에서 주어진 조건들을 파악해서 이해하는게 중요하다. 다행히도 문제에서 시뮬레이션 해야하는 행동에 대해서 정리해서 제시해줬고, 어떻게 구현할 지만 생각해보면 될 것 같다.
<ul>
<li>가장 처음에 아기 상어의 크기는 2이고, 아기 상어는 1초에 상하좌우로 인접한 한 칸씩 이동한다. -&gt; ㅇㅋ</li>
<li>아기 상어는 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없고, 나머지 칸은 모두 지나갈 수 있다. 아기 상어는 자신의 크기보다 작은 물고기만 먹을 수 있다. 따라서, 크기가 같은 물고기는 먹을 수 없지만, 그 물고기가 있는 칸은 지나갈 수 있다. -&gt; 지나갈 수 있는 칸과 먹을 수 있는 칸을 계산할 때 유의해야겠다.</li>
<li>더 이상 먹을 수 있는 물고기가 공간에 없다면 아기 상어는 엄마 상어에게 도움을 요청한다. -&gt; 모든 물고기 탐색을 탐색해야하고</li>
<li>먹을 수 있는 물고기가 1마리라면, 그 물고기를 먹으러 간다. -&gt; 밑에 규칙에서 자동으로 파생되어서 별 쓸모 없을 듯</li>
<li>먹을 수 있는 물고기가 1마리보다 많다면, 거리가 가장 가까운 물고기를 먹으러 간다. 거리는 아기 상어가 있는 칸에서 물고기가 있는 칸으로 이동할 때, 지나야하는 칸의 개수의 최솟값이다. -&gt; 물고기들의 최단거리를 계속 계산해나가야할 것 같다</li>
<li>거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기, 그러한 물고기가 여러마리라면, 가장 왼쪽에 있는 물고기를 먹는다. -&gt; 최단거리를 구할 때 이 규칙이 자동으로 적용되게 만들거나, 최단거리를 구하고 나서 이 규칙을 따로 적용해야겠다</li>
</ul>
<h2 id="풀이"><a href="#%ED%92%80%EC%9D%B4" aria-label="풀이 permalink"></a>풀이</h2>
일단 현재 아기상어와 물고기의 거리를 직선계산해서 최단거리를 구하고 소요시간을 구할 수는 없습니다. “지나갈 수 있는 칸”에 대한 제약이 있기 때문이죠.
곰곰히 생각하다가 BFS로 구하면 될 것 같았습니다. BFS는 큐에 한 depth의 원소들이 뭉쳐서 있기 때문에 가까이 있는 물고기들을 찾아나가기에 적합한 알고리즘 같습니다.
맨 처음 생각했을 때는 마지막 조건을 구현할 때 “대충 순회할 때 위, 왼쪽, 오른쪽, 아래 순서로 순회하면 되지 않을까?” 라고 생각했었는데 다행히도 예제 데이터에 그러면 틀리는 반례가 있었습니다. (이게 그 섣부른 그리디 판단? 인가 싶었어요) BFS로 물고기를 찾을 때 처리를 해줬습니다.
<h2 id="코드"><a href="#%EC%BD%94%EB%93%9C" aria-label="코드 permalink"></a>코드</h2>
<div data-language="python"><pre><code>from collections import deque
from typing import Tuple

class EdibleFishDoesNotExist(Exception):
 pass

Coord = Tuple[int, int]

directions = ((-1, 0), (0, -1), (0, 1), (1, 0))

# 입력
N = int(input())
board = [list(map(int, input().split())) for _ in range(N)]
shark_row, shark_col = None, None
shark_size = 2
eat_count = 0
timestamp = 0
for row in range(N):
 for col in range(N):
 if board[row][col] == 9:
 shark_row = row
 shark_col = col
 break
 if shark_row and shark_col:
 break

# 가장 가까운 먹을 수 있는(+ 문제의 우선순위 조건에 만족하는) 물고기의 칸과 그 물고기와 아기상어의 거리를 리턴합니다.
def get_nearest_edible_fish(shark_row, shark_col) -&gt; Tuple[Coord, int]:
 """
 :return (fish_row, fish_col), distance
 """
 queue = deque()
 visited = [[False]*N for _ in range(N)]
 
 #초기화
 queue.append((shark_row, shark_col, 0))
 board[shark_row][shark_col] = 0
 visited[shark_row][shark_col] = True

 candidates = []
 candidate_distance = None

 while queue:
 row, col, distance = queue.popleft()

 if candidate_distance and distance != candidate_distance:
 return sorted(candidates)[0], candidate_distance

 if 0 &lt; board[row][col] &lt; shark_size:
 if not candidate_distance:
 candidate_distance = distance
 candidates.append((row, col))
 
 for direction in directions:
 new_row = row + direction[0]
 new_col = col + direction[1]
 if new_row &gt;= N or new_col &gt;= N or new_row &lt; 0 or new_col &lt; 0 : continue
 if visited[new_row][new_col]: continue
 if board[new_row][new_col] &gt; shark_size: continue 
 visited[new_row][new_col] = True
 queue.append((new_row, new_col, distance + 1))
 
 if len(candidates) &gt; 0:
 return sorted(candidates)[0], candidate_distance
 
 raise EdibleFishDoesNotExist

while True:
 try:
 fish_to_eat, distance = get_nearest_edible_fish(shark_row, shark_col)
 shark_row, shark_col = fish_to_eat
 board[shark_row][shark_col] = 0
 timestamp += distance
 eat_count += 1
 if eat_count == shark_size:
 eat_count = 0
 shark_size += 1
 except EdibleFishDoesNotExist:
 print(timestamp)
 break</code></pre></div>
간단하게 <code>get_nearest_edible_fish</code>에서 BFS 템플릿 코드를 써서 구현하고, <code>EdibleFishDoesNotExist</code>가 나올 때 까지 루프를 도는 코드입니다.
그리고 <code>get_nearest_edible_fish</code>에서 같은 거리에 있는 물고기들 중 문제의 조건을 만족하는 물고기 한마리를 구하기 위한 아이디어는 다음과 같습니다.
<ul>
<li>BFS를 하면 (원소가 각 물고기의 최단거리라고 합시다) (1, 1, 1, 2, 2, 2, 3, 3, 3) 이런식으로 뭉쳐서 나온다. </li>
<li>처음 본 물고기가 1이면 1끼리 비교해서 가장 왼쪽 위에 있는 물고기를 구해야한다.</li>
<li>그래서 “맨 처음 발견한 물고기의 거리”(<code>candidate_distance</code>)를 저장해놓고 일단 발견한 물고기들을 <code>candidates</code>에다가 저장해놓는다.</li>
<li>물고기를 발견하다가 그 물고기의 거리와 <code>candidate_distance</code>가 다르면 <code>candidate_distance</code>인 물고기들을 모두 발견한 것이다.</li>
<li>가장 왼쪽 위라는 조건은 tuple을 기본 순서로 정렬했을 때 첫 번째 원소라는 것과 동치이다.</li>
<li>만약 (모두 순회했을 때 history)BFS 큐가 (1, 1, 1, 1, …) 이런식으로 구성되어있으면 <code>candidate_distance</code>가 달라지는 시점이 안올테니까 BFS 순회가 종료된 시점에서도 한 번 더 가장 왼쪽 위 조건을 검사해서 리턴.</li>
</ul></div></div>

cereme.dev

Sang yun Pae

https://www.acmicpc.net/problem/16236
BOJ 16236 아기상어 문제를 풀어봤습니다.
문제파악
구현문제들은 역시 문제에서 주어진 조건들을 파악해서 이해하는게 중요하다. 다행히도 문제에서 시뮬레이션 해야하는 행동에 대해서 정리해서 제시해줬고, 어떻게 구현할 지만 생각해보면 될 것 같다.
가장 처음에 아기 상어의 크기는 2이고, 아기 상어는 1초에 상하좌우로 인접한 한 칸씩 이동한다. -> ㅇㅋ
아기 상어는 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없고, 나머지 칸은 모두 지나갈 수 있다. 아기 상어는 자신의 크기보다 작은 물고기만 먹을 수 있다. 따라서, 크기가 같은 물고기는 먹을 수 없지만, 그 물고기가 있는 칸은 지나갈 수 있다. -> 지나갈 수 있는 칸과 먹을 수 있는 칸을 계산할 때 유의해야겠다.
더 이상 먹을 수 있는 물고기가 공간에 없다면 아기 상어는 엄마 상어에게 도움을 요청한다. -> 모든 물고기 탐색을 탐색해야하고
먹을 수 있는 물고기가 1마리라면, 그 물고기를 먹으러 간다. -> 밑에 규칙에서 자동으로 파생되어서 별 쓸모 없을 듯
먹을 수 있는 물고기가 1마리보다 많다면, 거리가 가장 가까운 물고기를 먹으러 간다. 거리는 아기 상어가 있는 칸에서 물고기가 있는 칸으로 이동할 때, 지나야하는 칸의 개수의 최솟값이다. -> 물고기들의 최단거리를 계속 계산해나가야할 것 같다
거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기, 그러한 물고기가 여러마리라면, 가장 왼쪽에 있는 물고기를 먹는다. -> 최단거리를 구할 때 이 규칙이 자동으로 적용되게 만들거나, 최단거리를 구하고 나서 이 규칙을 따로 적용해야겠다
풀이
일단 현재 아기상어와 물고기의 거리를 직선계산해서 최단거리를 구하고 소요시간을 구할 수는 없습니다. “지나갈 수 있는 칸”에 대한 제약이 있기 때문이죠.
곰곰히 생각하다가 BFS로 구하면 될 것 같았습니다. BFS는 큐에 한 depth의 원소들이 뭉쳐서 있기 때문에 가까이 있는 물고기들을 찾아나가기에 적합한 알고리즘 같습니다.
맨 처음 생각했을 때는 마지막 조건을 구현할 때 “대충 순회할 때 위, 왼쪽, 오른쪽, 아래 순서로 순회하면 되지 않을까?” 라고 생각했었는데 다행히도 예제 데이터에 그러면 틀리는 반례가 있었습니다. (이게 그 섣부른 그리디 판단? 인가 싶었어요) BFS로 물고기를 찾을 때 처리를 해줬습니다.
코드
from collections import deque
from typing import Tuple
class EdibleFishDoesNotExist(Exception):
 pass
Coord = Tuple[int, int]
directions = ((-1, 0), (0, -1), (0, 1), (1, 0))
# 입력
N = int(input())
board = [list(map(int, input().split())) for _ in range(N)]
shark_row, shark_col = None, None
shark_size = 2
eat_count = 0
timestamp = 0
for row in range(N):
 for col in range(N):
 if board[row][col] == 9:
 shark_row = row
 shark_col = col
 break
 if shark_row and shark_col:
 break
# 가장 가까운 먹을 수 있는(+ 문제의 우선순위 조건에 만족하는) 물고기의 칸과 그 물고기와 아기상어의 거리를 리턴합니다.
def get_nearest_edible_fish(shark_row, shark_col) -> Tuple[Coord, int]:
 """
 :return (fish_row, fish_col), distance
 """
 queue = deque()
 visited = [[False]*N for _ in range(N)]
 
 #초기화
 queue.append((shark_row, shark_col, 0))
 board[shark_row][shark_col] = 0
 visited[shark_row][shark_col] = True
 candidates = []
 candidate_distance = None
 while queue:
 row, col, distance = queue.popleft()
 if candidate_distance and distance != candidate_distance:
 return sorted(candidates)[0], candidate_distance
 if 0 < board[row][col] < shark_size:
 if not candidate_distance:
 candidate_distance = distance
 candidates.append((row, col))
 
 for direction in directions:
 new_row = row + direction[0]
 new_col = col + direction[1]
 if new_row >= N or new_col >= N or new_row < 0 or new_col < 0 : continue
 if visited[new_row][new_col]: continue
 if board[new_row][new_col] > shark_size: continue 
 visited[new_row][new_col] = True
 queue.append((new_row, new_col, distance + 1))
 
 if len(candidates) > 0:
 return sorted(candidates)[0], candidate_distance
 
 raise EdibleFishDoesNotExist
while True:
 try:
 fish_to_eat, distance = get_nearest_edible_fish(shark_row, shark_col)
 shark_row, shark_col = fish_to_eat
 board[shark_row][shark_col] = 0
 timestamp += distance
 eat_count += 1
 if eat_count == shark_size:
 eat_count = 0
 shark_size += 1
 except EdibleFishDoesNotExist:
 print(timestamp)
 break
간단하게 get_nearest_edible_fish에서 BFS 템플릿 코드를 써서 구현하고, EdibleFishDoesNotExist가 나올 때 까지 루프를 도는 코드입니다.
그리고 get_nearest_edible_fish에서 같은 거리에 있는 물고기들 중 문제의 조건을 만족하는 물고기 한마리를 구하기 위한 아이디어는 다음과 같습니다.
BFS를 하면 (원소가 각 물고기의 최단거리라고 합시다) (1, 1, 1, 2, 2, 2, 3, 3, 3) 이런식으로 뭉쳐서 나온다. 
처음 본 물고기가 1이면 1끼리 비교해서 가장 왼쪽 위에 있는 물고기를 구해야한다.
그래서 “맨 처음 발견한 물고기의 거리”(candidate_distance)를 저장해놓고 일단 발견한 물고기들을 candidates에다가 저장해놓는다.
물고기를 발견하다가 그 물고기의 거리와 candidate_distance가 다르면 candidate_distance인 물고기들을 모두 발견한 것이다.
가장 왼쪽 위라는 조건은 tuple을 기본 순서로 정렬했을 때 첫 번째 원소라는 것과 동치이다.
만약 (모두 순회했을 때 history)BFS 큐가 (1, 1, 1, 1, …) 이런식으로 구성되어있으면 candidate_distance가 달라지는 시점이 안올테니까 BFS 순회가 종료된 시점에서도 한 번 더 가장 왼쪽 위 조건을 검사해서 리턴.

백준 16236 아기상어 with Python3

댓글