문제 출처

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. 상어는 본인의 크기만큼의 물고기를 먹었을 때 크기가 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. 비고 (실패사례)

처음에는 먹을 수 있는 물고기를 추린 후에, 각각의 물고기에 대해 거리를 측정하였다. 그러나 이런 식으로 한다면 물고기 한 마리마다 BFS와 $O(n^2)$의 행렬 초기화가 반복되기 때문에 시간이 굉장히 오래 걸린다.

따라서 각각의 물고기에 대해 길을 찾는 것 대신에 모든 물고기에 대해 한 번의 길을 찾고, 먹을 수 있는 물고기를 찾았을 때 길찾기를 종료하는 것으로 바꿔 문제를 풀었다.

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)