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

16236번: 아기 상어

 

문제 내용

시간 제한 : 2 초

메모리 : 512 MB

 

공간

• NxN 크기의 공간

등장인물

• 물고기 M마리, 각 크기는 1~6으로 입력 주어짐
• 아기상어 1마리, 최초 크기 2

동작

아기상어가 1초에 상하좌우로 이동한다. 아래의 제약 조건 있음.

• 자기보다 크기가 큰 물고기 : 못먹음, 지나가기 가능
• 크기 같은 물고기 : 못먹음, 지나가기 가능
• 크기 작은 물고기 : 먹음. 지나가기 가능
  아기상어 현재 크기만큼 물고기 (개수) 먹으면 아기상어 크기+1

종료 조건

• 더 이상 먹을 물고기 없다 = 엄마 상어에게 Help 요청하고 종료
• 고기 1마리 남음 : 무조건 그물고기 먹으러
• 고기 2마리 이상 : 가장 가까운 물고기 먹으러간다.
  가장 가까운 물고기 2마리 이상이면 x 작은순. 그게 또 2마리 이상이면 y작은 순

 

입력

첫째 줄에 공간의 크기 N(2 ≤ N ≤ 20)이 주어진다.

둘째 줄부터 N개의 줄에 공간의 상태가 주어진다. 공간의 상태는 0, 1~6, 9로 이루어져 있고,

아래와 같은 의미를 가진다.

• 0: 빈 칸
• 1, 2, 3, 4, 5, 6: 칸에 있는 물고기의 크기
• 9: 아기 상어의 위치

아기 상어는 공간에 한 마리 있다.

 

출력

첫째 줄에 아기 상어가 엄마 상어에게 도움을 요청하지 않고 물고기를 잡아먹을 수 있는 시간을 출력한다.

 

예제 입력 1

3

0 0 0

0 0 0

0 9 0

 

예제 출력 1 

0

 

예제 입력 2

6
6 0 6 0 6 1
0 0 0 0 0 2
2 3 4 5 6 6
0 0 0 0 0 2
0 2 0 0 0 0
3 9 3 0 0 1

 

예제 출력 1 

48

유형

• 구현
• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색
• 시뮬레이션

---

풀이

아기상어가 신나게 물고기 먹방하는 문제다.

구현 시 아주 조심해야될 포인트만 짚어주겠다.

1. 매 탐색마다 "모든" 물고기까지 거리를 구할 필요 없다. 시간 초과난다.
2. BFS 탐색 시 "현재 경로가 항상 최적"이라는 것을 이용한다.
   즉, 물고기를 한 번이라도 만나면 무조건 그 물고기 까지가 최단거리이다.
   만약 최단거리가 동일한 물고기가 2마리 이상이면, X작은순, Y작은순으로 정렬하고, 맨 앞 물고기 먹는다.
   
3. 아기상어 위치가 좌표상에 9로 주어지는데 혹시 0으로 바꾸지 않고 탐색을 했는지 확인하라.
   나중에 9라서 못지나간다. (혹은 아기상어의 위치 update가 잘 되고있는지 확인)
   

import sys,collections
shark_x, shark_y = 0,0
shark_size = 2
eat_cnt = 0
fish_cnt = 0
fish_pos = []
time = 0
dx = (0,0,1,-1)
dy = (1,-1,0,0)
n = int(sys.stdin.readline())
board = [list(map(int,sys.stdin.readline().split())) for _ in range(n)]
for i in range(n):
    for j in range(n):
        if 0 < board[i][j] <=6:
            fish_cnt +=1
            fish_pos.append((i,j))
        elif board[i][j] == 9:
            shark_x, shark_y = i,j
board[shark_x][shark_y]=0

def bfs(shark_x,shark_y):
    q = collections.deque([(shark_x,shark_y,0)])
    dist_list = []
    visited = [[False]*n for _ in range(n)]
    visited[shark_x][shark_y] = True
    min_dist = int(1e9)
    while q:
        x,y,dist = q.popleft()
        for i in range(4):
            xx = dx[i]+x
            yy = dy[i]+y
            if 0<=xx<n and 0<=yy<n and not visited[xx][yy]:
                if board[xx][yy] <= shark_size:
                    visited[xx][yy] = True
                    if 0<board[xx][yy]<shark_size:
                        min_dist = dist
                        dist_list.append((dist+1,xx,yy))
                    if dist+1 <= min_dist:
                        q.append((xx,yy,dist+1))
    if dist_list:
        dist_list.sort()
        return dist_list[0]
    else:
        return False

while fish_cnt :
    result = bfs(shark_x,shark_y)
    if not result:
        break
    shark_x,shark_y = result[1],result[2]
    time +=result[0]
    eat_cnt+=1
    fish_cnt-=1
    if shark_size == eat_cnt:
        shark_size +=1
        eat_cnt =0
    board[shark_x][shark_y] = 0

print(time)