아기 상어 [백준 16236] - python

 

import heapq

def BOJ16236() :
  n = int(input())
  graph = []
  q = []

  for i in range(n) :
    line = list(map(int, input().split()))
    graph.append(line)
    for j in range(len(line)) :
      if line[j] == 9 :
        heapq.heappush(q, (0, i, j))
        graph[i][j] = 0

  direction = [[0,1], [0,-1], [1,0], [-1,0]]
  result = 0
  body, eat = 2, 0
  visited =[[0] * n for _ in range(n)]

  while q :
    dist, curr_x, curr_y = heapq.heappop(q)

    if 0 < graph[curr_x][curr_y] < body :
      eat += 1
      graph[curr_x][curr_y] = 0
      if body == eat :
        eat = 0
        body += 1
      result += dist
      dist = 0
      q = []
      visited =[[0] * n for _ in range(n)]

    for dir in direction :
      dir_x, dir_y = dir
      next_x = dir_x + curr_x
      next_y = dir_y + curr_y
      if 0 <= next_x < n and 0 <= next_y < n and 0 <= graph[next_x][next_y] <= body and visited[next_x][next_y] == 0:
        visited[next_x][next_y] = True
        heapq.heappush(q, (dist+1, next_x, next_y))

  print(result)

BOJ16236()

 

접근 방법 : 

1. heapq를 활용해야 한다. 

아기 상어가 물고기를 먹으러 갈때 제약사항이 있다. 
1) 거리가 가장 가까운 물고기 여야 할것

2) 거리가 가까운 물고기가 여러개라면 가장 위쪽에 있는 물고기 여야 할것

3) 거리가 가까운 물고기가 여러개라면 가장 왼쪽에 있는 물고기 여야 할것

=> 새로 탐색 하게 되는 물고기는 우선순위가 3개의 기준이 되어 정렬이 된채로 들어오면 다음 물고기를 효율적으로 탐색할 수 있을 것이다 -> heapq를 활용하여 값이 들어오면서 동시에 정렬이 되게 하여 효율을 높이자

 

2. !핵심 => heapq를 이용하여 첫번째 먹을수 있는 물고기에 접근하면 모든 방문 기록을 초기화 해준다.

=> bfs를 이용하면 물고기가 여러마리가 생기는 것과 같은 현상이다. 단 한마리의 움직임을 형상화 하기 위해 물고기를 잡아먹게 되면 방문기록을 초기화 시켜줘서 다음 물고기까지의 탐색을 시작하여야 한다. 이때 방문기록이 초기화가 되어있지 않다면 물고기를 잡아먹은후 아기상어는 갈곳이 없거나 적어질 것이다.

 

3. heapq를 이용해서 알맞게 탐색하면 된다.

 

---

먼저 선행되어야 하는 작업이 존재 한다 => 위상정렬

값의 우선순위에 따라 수행해야 하는 작업들의 순서가 달라질 수 있다 => 기본 그래프 탐색 + heapq 모듈 이용

---

장애물 이였던 것 :

1. heapq의 개념을 떠올리기 어려웠고 사용법에도 익숙치 않았다. 이러한 측면에서 해당 문제는 잘 만난것 같다. 
   python의 heapq 모듈은 list를 heap의 구조로 변환하여 다뤄주는 것이고 heap은 순서가 정렬되어있는 트리 자료구조 이다.

 

a[k] -> a[2k+1] a[2k +2], k번째 인덱스에서 가지는 두개가 나오게 된다. 

새로운 숫자를 넣었을 경우 logn의 시간복잡도로 위치를 찾게 된다.

 

heapq는 기본적으로 오름차순 정렬이다.  (값에 임의로 - 부호를 붙여서 내림차순 정렬로 활용할 수도 있다.)

 

그리고 정렬의 방식은

첫번째 인자가 작은것,

첫번째 인자가 같으면 두번째 인자가 작은것,

두번째 인자가 같으면 세번째 인자가 작은것 순으로 정렬이 된다.

결과 화면에서 나중에 push를 해준값이 먼저 정렬되어 있는 모습을 확인할 수 있다.

 

 

출처 : https://www.acmicpc.net/problem/16236

16236번: 아기 상어