[백준] 16236번 - 아기상어 / 골드4 / 파이썬 풀이

문제 링크

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

16236번: 아기 상어

시간 제한 : 2초

메모리 제한 : 512 MB

 

문제 요약

• NxN 크기의 공간
• 물고기 M마리, 각 크기는 1~6 (입력 주어짐)
• 아기상어 1마리, 최초 크기 2, 최초 위치가 숫자 9로 정해짐 (입력 주어짐)
  동작 : 1초에 상화좌우중 한 곳으로 한 칸씩 이동
• 아기상어 제약조건
  - 자기보다 크기가 큰 물고기 : 못 먹음. 지나가기 불가능.
  - 자기랑 크기가 같은 물고기 : 못 먹음. 지나가기 가능.
  - 자기보다 크기가 작은 물고기 : 먹음. 지나가기 가능.
  - 아기상어의 현재 크기만큼 물고기 마릿수(물고기 크기 상관 X)를 먹으면 아기상어의 크기 1 증가.
  - 가장 가까운 물고기부터 먹는다. 가장 가까운 물고기가 여러 마리라면, 윗쪽부터. 그 다음은 왼쪽 순.
  
  
• 문제 : 공간의 상태가 주어졌을 때, 아기 상어가 몇 초 동안 엄마 상어에게 도움을 요청하지 않고 물고기를 잡아먹을 수 있는지 구하는 프로그램 작성.
  
  
• 종료 조건
  - 더이상 먹을 물고기가 없다 => 엄마 상어에게 도움을 요청함. => 종료
  - 물고기가 1 마리 남음 => 그 물고기 먹으러 감. => 종료
  
  

입력

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

둘째 줄부터 N개의 줄에 공간의 상태가 주어진다. 공간의 상태는 0, 1, 2, 3, 4, 5, 6, 9로 이루어져 있고, 아래와 같은 의미를 가진다.

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

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

 

출력

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

 

예제 1

예제 2

예제 3

 

예제 4

---

풀이

 

"BFS 탐색 시 현재 경로가 항상 최적이라는 것을 이용!"

import sys, collections

shark_x, shark_y = 0, 0
shark_size = 2
eat_cnt = 0

fish_cnt = 0
fish_pos = []

time = 0

dx = (1, -1, 0, 0)
dy = (0, 0, 1, -1)

n = int(sys.stdin.readline())	# NxN 크기의 공간 입력받기.
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)					# int를 무한대로 지정하는 방법 중에 하나.
    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]:		# (xx, yy) 위치에 물고기가 있고, 아직 방문하지 않았다면
            	if board[xx][yy] <= shark_size:		# (xx,yy) 위치의 물고기가 아기상어보다 작거나 같다면
                	visited[xx][yy] = True			# 아기상어를 (xx,yy) 위치로 이동.
                    if 0< board[xx][yy] < shark_size:		# (xx,yy) 위치의 물고기 크기가 아기상어보다 작다면
                    	min_dist = dist						# 지금까지 상어가 이동한 거리를 min_dist로 설정.
                        dist_list.append((dist+1, xx, yy))	# 상어가 이동한 거리 및 위치 저장.
                    if dist+1 <= min_dist:					
                    	q.append((xx, yy, dist+1))			# 상어가 다음 턴에 이동할 인접한 좌표 및 최소거리 deque에 추가.
     if dist_list:
     	dist_list.sort()	# dist_list[0]으로 상어가 이동한 총 거리 쉽게 추출하기 위해서 정렬.
        return dist_list[0]	# 상어가 이동한 총 거리 및 현재 상어 위치 return.
     else:
     	return False
        
 while fish_cnt:
 	result = bfs(shark_x, shark_y)
    if not result:
    	break
    shar_x, shark_y = result[1], result[2]
    time += result[0]
    eat_cnt += 1		# 먹은 물고기 수 카운트하여 상어 크기 측정하깅 위함.
    fish_cnt -= 1		# while문 1번에 물고기 한마리 먹는다.
    if shark_size == eat_cnt:
    	shark_size += 1
        eat_cnt = 0
    board[shark_x][shark_y] = 0
    
print(time)

 

참고

https://11001.tistory.com/96

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