백준 - 16236 아기상어 (파이썬)

문제 링크 : https://www.acmicpc.net/problem/16236
난이도 : 골드 3

문제풀이

---

문제 정리

• 작은 물고기만 먹을 수 있음

• 같은 사이즈의 물고기는 지나갈 수만 있음

• 먹을 수 있는 물고기가 1마리라면, 그 물고기를 먹으러 간다.

  • 먹을 수 있는 물고기가 1마리보다 많다면, 거리가 가장 가까운 물고기를 먹으러 간다
  • 거리는 아기 상어가 있는 칸에서 물고기가 있는 칸으로 이동할 때, 지나야하는 칸의 개수의 최솟값이다.
  • 거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기, 그러한 물고기가 여러마리라면, 가장 왼쪽에 있는 물고기를 먹는다.

• 자신의 크기와 같은 수의 물고기를 먹을 때 마다 크기가 1 증가한다

• 상어크기가 2면 2마리 먹어야함

분석

1. 문제에서는 아기 상어가 어미의 도움없이 몇 초간 혼자 사냥할 수 있는지 묻는다
2. 아기상어는 사냥시 주변에서 가장 가까운 먹이를 탐색하게 되고, 거리가 같은 경우 조건대로 움직이게된다.
3. 가까운 먹이를 찾는 탐색 문제이기 때문에 BFS를 생각해 볼 수 있다.
4. BFS를 사용할 시 입력으로는 현재 아기 상어의 위치를 생각할 수 있고, 출력으로는 후보를 리스트를 반환 해야한다.

   가장 가까운 거리에 있는 먹이가 여러 개 일 수 있기 때문이다.

5. 간선은 상하 좌우지만 조건에 따라서 움직이기 때문에 조건을 상세하여야한다.
6. 후보 리스트는 우선 순위가 있기 때문에 정렬을 사용할 수 있다.
7. 후보리스트가 나오면 맨 앞의 후보 먹이를 뽑아 그 위치로 이동한다.
8. 맨 앞의 후보만 먹고 위치 이동후 다시 BFS 해야한다

   먹이의 위치로 이동했을때 새로운 먹이 후보군의 우선순위가 또 달라지기 때문이다

9. 몇 개를 먹었는지 몇 초간 이동했는지 체크해 줄 필요가 있다.

시간복잡도

• BFS의 시간복잡도는 간선 + 노드의 수로 결정된다.
• 먹이 후보를 한번 탐색시(BFS) 간선(400*4) + 노드 400 = 2000 정도 된다.
• 탐색 후 바뀐 가능한 모든 위치에서의 시간복잡도는 400 * 2000 = 80만 정도 이다.
• 안정적으로 문제를 풀 수 있을거라 예상된다.

전체코드

---

from collections import deque

N = int(input())
space = [list(map(int, input().split())) for _ in range(N)]

dx, dy = [-1, 0, 1, 0], [0, 1, 0, -1]

pos = []
for i in range(N):
    for j in range(N):
        if space[i][j] == 9:
            pos.append(i)
            pos.append(j)

cnt = 0

# 3. 가까운 먹이를 찾는 탐색 문제이기 때문에 `BFS`를 생각해 볼 수 있다.
# 4. BFS를 사용할 시 입력으로는 현재 아기 상어의 위치를 생각할 수 있고,
# 	 출력으로는 후보를 리스트를 반환 해야한다.
def bfs(x, y):
    visited = [[0]*N for _ in range(N)]
    queue = deque([[x,y]])
    cand = []

    visited[x][y] = 1

    while queue:
        i, j = queue.popleft()

        for idx in range(4):
            ii, jj = i + dx[idx] , j + dy[idx]

            if 0 <= ii and ii < N and 0 <= jj and jj < N and visited[ii][jj] == 0:
				# 5. 간선은 상하 좌우지만 조건에 따라서 움직이기 때문에 조건을 상세하여야한다.
                if space[x][y] > space[ii][jj] and space[ii][jj] != 0:
                    visited[ii][jj] =  visited[i][j] + 1
                    cand.append((visited[ii][jj] - 1, ii, jj))
                elif space[x][y] == space[ii][jj]:
                    visited[ii][jj] =  visited[i][j] + 1
                    queue.append([ii,jj])
                elif space[ii][jj] == 0:
                    visited[ii][jj] =  visited[i][j] + 1
                    queue.append([ii,jj])
                    
	# 6. 후보 리스트는 우선 순위가 있기 때문에 정렬을 사용할 수 있다.
    return sorted(cand, key = lambda x: (x[0], x[1], x[2]))


i, j = pos
size = [2, 0]
# 8. 맨 앞의 후보만 먹고 위치 이동후 다시 BFS 해야한다
while True:
    space[i][j] = size[0]
    cand = deque(bfs(i,j))
    
    if not cand:
        break
        
    # 7. 후보리스트가 나오면 맨 앞의 후보 먹이를 뽑아 그 위치로 이동한다.
    step, xx, yy = cand.popleft()
    cnt += step
    size[1] += 1
    
	# 9. 몇 개를 먹었는지 몇 초간 이동했는지 체크해 줄 필요가 있다.
    if size[0] == size[1]:
        size[0] += 1
        size[1] = 0

    space[i][j] = 0
    i, j = xx, yy
        
print(cnt)

정리 및 느낀점

---

• 난이도가 올라갈수록 단순 알고리즘에서 다른 알고리즘을 섞을 수 있음
• 바텀 업 vs 탑 다운 중 고민
  • 어려울수록 탑 다운 (내 생각)
• 그래프 문제는 쉬울 수록 조건 없는 간선을 주는데 어려울 수록 조건 있는 간선을 주는 듯
• 탐색조건의 구체화
• 조건에 매달리지말고 큰 틀을 잡고 세부조건을 구현하자
• 문제에서 어떤 알고리즘을 쓸 지 파악하는게 중요
• 해당 문제는 그래프에서 최단거리이기 때문에 BFS를 떠올려 볼 수 있었음