[16236] 아기상어 (1) _ 문제 설명 & 일부 코드 설명

문제 해설 :

 

N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 

공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다.

아기 상어와 물고기는 모두 크기를 가지고 있고, 이 크기는 자연수이다.

가장 처음에 아기 상어의 크기는 2이고, 아기 상어는 1초에 상하좌우로 인접한 한 칸씩 이동한다.

 

아기 상어는 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없고, 나머지 칸은 모두 지나갈 수 있다. 

아기 상어는 자신의 크기보다 작은 물고기만 먹을 수 있다.

따라서, 크기가 같은 물고기는 먹을 수 없지만, 그 물고기가 있는 칸은 지나갈 수 있다.

 

 

아기 상어가 어디로 이동할지 결정하는 방법은 아래와 같다.

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

=> 대충 BFS를 하라는 얘기다. (BFS)로직에 들어간다.

 

아기 상어의 이동은 1초 걸리고, 물고기를 먹는데 걸리는 시간은 없다고 가정한다. 

즉, 아기 상어가 먹을 수 있는 물고기가 있는 칸으로 이동했다면, 이동과 동시에 물고기를 먹는다.

물고기를 먹으면, 그 칸은 빈 칸이 된다.

 

아기 상어는 자신의 크기와 같은 수의 물고기를 먹을 때 마다 크기가 1 증가한다.

예를 들어, 크기가 2인 아기 상어는 물고기를 2마리 먹으면 크기가 3이 된다.

 

공간의 상태가 주어졌을 때, 아기 상어가 몇 초 동안 엄마 상어에게 도움을 요청하지 않고 물고기를 잡아먹을 수 있는지 구하는 프로그램을 작성하시오.  =>프로그램 종료 조건, 및 출력 조건

=============================

 

전체 로직은 이렇게 생각할 수 있겠다.

순서도로 그려야하는게 맞지만... 좀 귀찮았따.

 

n = int(input())
board = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
#2차원 배열 입력받는 코드


#보드의 값을 수정하는
for i in range(n):
    for j in range(n):
        if 0 < board[i][j] <= 6: #물고기 수 및 위치 선정
            fish_count += 1
            fish_position.append((i, j))
        elif board[i][j] == 9:   #상어의 위치
            shark_x, shark_y = i, j #상어의 좌표를 데이터로 넘겨줌

board[shark_x][shark_y] = 0 #9로 표시된 상어를 변경하지 않으면, 9를 다른 물고기로 판정한다.

 

while fish_count:
    result = bfs(shark_x, shark_y)
    if not result:
        break
    shark_x, shark_y = result[1], result[0]
    time += result[0]

    #fish count
    eat_count += 1
    fish_count -= 1

    if shark_size == eat_count:
        shark_size += 1
        eat_count = 0
    board[shark_x][shark_y] = 0

print(time)

 

상어가 움직이는 메인로직 코드 

 

이제 여기서 (2)편에서 bfs코드를 설명과 함께 뜯어보겠다.

 

 

 

#파이썬, 백준, 16236, 골드3

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