[백준] 16236번: 아기 상어 - 파이썬(python)

 

 

 

나의 풀이

from collections import deque

n= int(input())
arr = []
now_x , now_y = -1, -1 # 아기 상어의 위치
length = 2 # 아기 상어의 크기
cnt = 0 # 아기 상어가 먹은 물고기 개수
time = 0 # 아기 상어가 물고기를 잡아먹는데 걸린 시간
m = 0 # 물고기 개수

for _ in range(n) :
  arr.append(list(map(int, input().split())))

for i in range(n) :
  for j in range(n) :
    if arr[i][j] == 9 :
      now_x = i
      now_y = j
      arr[i][j] = 0
    elif arr[i][j] > 0 :
      m += 1

dx = [1,0,-1,0]
dy = [0,1,0,-1]
# 현재 위치에서 먹을 수 있는 가장 가까운 물고기 위치 리턴
def bfs(x,y) :
  min_dist = 1e9
  q = deque([(now_x,now_y,0)])
  visited = [[False] * n for _ in range(n)]
  visited[x][y] = True
  fish = []
  
  while q :
    fx,fy,dist = q.popleft()
    
    if 0 < arr[fx][fy] < length : # 먹을 수 있는 물고기
      min_dist = dist
      fish.append((dist,fx,fy))
      
    for i in range(4) :
      nx = fx+dx[i]
      ny = fy+dy[i]
      if dist+1 <= min_dist and 0<=nx<n and 0<=ny<n and arr[nx][ny]<=length and not visited[nx][ny] :
        visited[nx][ny] = True
        q.append((nx,ny,dist+1))
        
  if fish == [] :
    return False
  else :
    fish.sort()
    return fish[0]

while m > 0 :
  fish = bfs(now_x,now_y)
  if fish == False :
    break
    
  now_x,now_y = fish[1],fish[2]
  arr[now_x][now_y] = 0
  time += fish[0]
  m -= 1 # 남아있는 물고기 개수 1 감소
  cnt += 1 # 아기상어가 먹은 물고기 개수 1 증가
  
  if cnt == length : # 아기상어가 먹은 물고기개수가 몸길이가 된다면
    length += 1
    cnt = 0
    
print(time)

단순한 BFS 문제라고 생각했는데, 꽤 어려워서 시간이 많이 소요된 문제이다.

역시 아직 갈 길이 멀다는 것을 또 한번 느낀다.

 

 

문제를 풀기 위한 단계는 다음과 같다.

Step 1

for _ in range(n) :
  arr.append(list(map(int, input().split())))

for i in range(n) :
  for j in range(n) :
    if arr[i][j] == 9 :
      now_x = i
      now_y = j
      arr[i][j] = 0
    elif arr[i][j] > 0 :
      m += 1

입력받은 위치 x,y 의 값이 9라면, 아기 상어의 위치이다.

따라서 현재 x,y위치를 해당 위치로 초기화하고, arr[x][y] 를 0으로 변경한다.

또한, 0<arr[x][y]<9 라면 물고기가 위치하는 칸으로, 물고기의 개수를 세어준다.

 

 

Step 2

while m > 0 :
  fish = bfs(now_x,now_y)
  if fish == False :
    break
    
  now_x,now_y = fish[1],fish[2]
  arr[now_x][now_y] = 0
  time += fish[0]
  m -= 1 # 남아있는 물고기 개수 1 감소
  cnt += 1 # 아기상어가 먹은 물고기 개수 1 증가
  
  if cnt == length : # 아기상어가 먹은 물고기개수가 몸길이가 된다면
    length += 1
    cnt = 0

물고기의 개수가 0 일때까지 현재 위치에서 가장 가까운 물고기의 위치를 찾고, 해당 위치로 이동하는 과정을 반복한다.

BFS 로 현재 위치에서 가장 가까운 물고기의 위치를 찾고, 만약 물고기가 존재하지 않는다면 반복문을 종료한다.

물고기가 존재한다면, 현재 위치를 해당 물고기의 위치로 갱신하고, 물고기까지 이동하는데 걸린 시간을 time 에 추가한다.

그리고 남아있는 물고기 개수를 -1, 아기상어가 먹은 물고기 개수를 +1 로 변경한다.

만약, 아기상어가 먹은 물고기개수가 아기상어의 몸길이가 된다면 몸길이를 1 증가시키고, 다시 아기상어가 먹은 물고기 개수를 0 으로 초기화한다.

• * 여기서 나는 큰 실수를 저질렀다
• 아기상어가 먹은 물고기개수가 아기상어의 몸길이가 되면, 몸길이만 1증가되고, 먹은 물고기 개수는 계속 유지된다고 착각한 것이다...!
• 그러나 현재 몸길이가 2이고, 먹은 물고기 개수가 2라면 몸길이는 3이 되고, 먹은 물고기 개수는 다시 0 이 되어야 한다.
• 즉, 몸길이가 3->4 로 증가하기 위해서는 다시 물고기 3개를 먹어야 하는 것이다.
• 나는 여기서 먹은 물고기를 2로 유지하여, 1개의 물고기만 추가로 먹어도 몸길이가 4로 증가되도록 구현하는 오류를 범했다...

 

 

Step 3

dx = [1,0,-1,0]
dy = [0,1,0,-1]
# 현재 위치에서 먹을 수 있는 가장 가까운 물고기 위치 리턴
def bfs(x,y) :
  min_dist = 1e9
  q = deque([(now_x,now_y,0)])
  visited = [[False] * n for _ in range(n)]
  visited[x][y] = True
  fish = []
  
  while q :
    fx,fy,dist = q.popleft()
    
    if 0 < arr[fx][fy] < length : # 먹을 수 있는 물고기
      min_dist = dist
      fish.append((dist,fx,fy))
      
    for i in range(4) :
      nx = fx+dx[i]
      ny = fy+dy[i]
      if dist+1 <= min_dist and 0<=nx<n and 0<=ny<n and arr[nx][ny]<=length and not visited[nx][ny] :
        visited[nx][ny] = True
        q.append((nx,ny,dist+1))
        
  if fish == [] :
    return False
  else :
    fish.sort()
    return fish[0]

현재 위치에서 가장 가까운 물고기 위치를 리턴해주는 BFS 함수이다.

해당 함수는 보통의 BFS 구현방법과 일치하다.

현재 위치를 dequeue 에 초기화하고, 큐가 빌때까지 반복하는 함수이다.

 

만약, 큐에서 popleft() 한 칸에 물고기가 존재한다면, 해당 칸까지 걸린 dist(거리) 값을 min_dist 값으로 갱신하고, fish리스트에 해당 위치와 거리를 추가한다. 

 

현재 위치에서 상하좌우를 확인하면서, 다음으로 이동할 칸이 0~n-1 까지의 범위이면서, 칸의 값이 몸길이 이하이고, 방문하지 않았으면 이동하도록 조건을 추가한다.

그러나 다른 BFS 와 다르게 더 추가한 조건이 존재한다. 

만약 dist+1 (다음 칸으로 이동하는데 걸리는 시간, 거리, 비용) 이 min_dist 보다 크다면 큐에 넣지 않는 것이다!

즉, 이미 구해놓은 물고기 위치까지의 거리보다 더 큰 값이므로, 어짜피 가장 가까운 물고기가 될 수 없는 경우이기 때문이다!!!!

 

모든 작업을 완료했다면, fish[] 를 정렬하여 리턴해준다.

fish에 들어있는 값들은 물고기들의 후보로, 각 원소는 (비용,x,y) 로 이루어져 있어 정렬시 비용,x,y 의 오름차순으로 정렬된다.