https://www.acmicpc.net/problem/16236
문제 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다.
아기 상어와 물고기는 모두 크기를 가지고 있고, 이 크기는 자연수이다. 가장 처음에 아기 상어의 크기는 2이고, 아기 상어는 1초에 상하좌우로 인접한 한 칸씩 이동한다.
아기 상어는 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없고, 나머지 칸은 모두 지나갈 수 있다. 아기 상어는 자신의 크기보다 작은 물고기만 먹을 수 있다. 따라서, 크기가 같은 물고기는 먹을 수 없지만, 그 물고기가 있는 칸은 지나갈 수 있다.
아기 상어가 어디로 이동할지 결정하는 방법은 아래와 같다.
더 이상 먹을 수 있는 물고기가 공간에 없다면 아기 상어는 엄마 상어에게 도움을 요청한다. 먹을 수 있는 물고기가 1마리라면, 그 물고기를 먹으러 간다. 먹을 수 있는 물고기가 1마리보다 많다면, 거리가 가장 가까운 물고기를 먹으러 간다. 거리는 아기 상어가 있는 칸에서 물고기가 있는 칸으로 이동할 때, 지나야하는 칸의 개수의 최솟값이다. 거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기, 그러한 물고기가 여러마리라면, 가장 왼쪽에 있는 물고기를 먹는다. 아기 상어의 이동은 1초 걸리고, 물고기를 먹는데 걸리는 시간은 없다고 가정한다. 즉, 아기 상어가 먹을 수 있는 물고기가 있는 칸으로 이동했다면, 이동과 동시에 물고기를 먹는다. 물고기를 먹으면, 그 칸은 빈 칸이 된다.
아기 상어는 자신의 크기와 같은 수의 물고기를 먹을 때 마다 크기가 1 증가한다. 예를 들어, 크기가 2인 아기 상어는 물고기를 2마리 먹으면 크기가 3이 된다.
공간의 상태가 주어졌을 때, 아기 상어가 몇 초 동안 엄마 상어에게 도움을 요청하지 않고 물고기를 잡아먹을 수 있는지 구하는 프로그램을 작성하시오.
전형적인 BFS류의 탐색과 조건에 상어를 움직여야하는 시뮬레이션 문제입니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
from collections import deque
INF = 1e9 #무한을 의미하는 값으로 10억 설정
#맵의 크기 N을 입력받기
n = int(input())
#전체 모든 칸에 대한 정보 입력
array = []
for i in range(n):
array.append(list(map(int,input().split())))
#아기 상어의 현재 크기 변수와 현재 위치 변수
now_size = 2
now_x, now_y = 0, 0
#아기 상어의 시작 위치를 찾은 뒤에 그 위치엔 아무것도 없다고 처리
for i in range(n):
for j in range(n):
if array[i][j] == 9:
now_x, now_y = i,j
array[now_x][now_y] = 0
dx = [-1,0,1,0]
dy = [0,1,0,-1]
하나하나 살펴보겠습니다. 우리는 deque를 이용해서 이동 경로를 관리를 할려고 합니다.
맵의 위치와 전체 칸에 대한 정보를 입력을 받고 조건에 주어진 대로 상어의 크기는 2로 시작을 하고 아직 상어의 위치는 입력을 받기 전에는 0으로 해줍시다.
그리고 지도를 입력을 받았다면 상어의 위치와 해당 하는 곳은 0으로 해줍시다. 우리에게 필요한 것은 상어가 현재 어디에 있는가이지 그 위치는 고정되어 있지 않기 때문입니다.
그리고 상어는 상하좌우로 이동할 수 있으니 dx, dy를 지정을 합시다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#모든 위치까지의 '최단 거리만' 계산하는 BFS함수
def bfs():
#값이 -1이라면 도달할 수 없다는 의미(초기화)
dist = [[-1]*n for _ in range(n)]
#시작 위치는 도달이 가능하다고 보며 거리는 0
q = deque([(now_x,now_y)])
dist[now_x][now_y] = 0
while q:
x,y = q.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx and nx<n and 0 <= ny and ny < n:
#자신의 크기보다 작거나 같은 경우에 지나갈 수 있음
if dist[nx][ny] == -1 and array[nx][ny] <= now_size:
dist[nx][ny] = dist[x][y] + 1
q.append((nx,ny))
#모든 위치까지의 최단 거리 테이블 반환
return dist
상어가 먹이를 찾기 위한 최단 거리를 구합니다. 일단 모든 위치를 도달 할 수 없다는 의미의 -1로 초기화를 합시다. 그러면 기존 지도크기에 모든 값이 -1인 2차원배열이 생성이 됩니다.
이제 큐로 이동 경로를 관리합시다. 현재 q에는 현재 상어의 위치가 있습니다. 그리고 그 위치는 0 이동 가능한 지점입니다.
큐는 들어온 순서대로 나가기 때문에 popleft를 사용을 합니다. 그러면 첫번째로는 상어의 위치 now_x, now_y가 들어갑니다. 이어서 총 상어는 4방향으로 움직일 수 있는데 이를 nx,ny로 표시를 합시다. 그리고 nx와 ny의 허용범위(지도안)일 때만 확인을 하는데 일단 지도를 -1로 초기화를 했습니다. 그리고 해당 하는 위치가 자기의 크기와 작거나 같을때만 탐색을 할 수 있습니다. 이제 이동한 위치는 이전 위치에서 경로 비용이 1이 추가된 비용을 업데이트하고 이를 큐에 넣어줍니다.
이제 모든 위치까지의 최단 거리 테이블이 반환이 됩니다. 그러니까 각 위치까지 도달할때 필요한 최단 거리를 구하는 함수이고 아직 상어가 물고기를 몇 마리 이상 먹었을때라거나 조건이 반영되지 않았습니다. 다음 함수에서 살펴봅시다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#최단 거리 테이블이 주어졌을 때, 먹을 물고기를 찾는 함수
def find(dist):
x, y = 0,0
min_dist = INF
for i in range(n):
for j in range(n):
#도달이 가능하면서 먹을 수 있는 물고기 일때
if dist[i][j] != -1 and 1 <= array[i][j] and array[i][j] < now_size:
#가장 가까운 물고기 1마리만 선택
if dist[i][j] < min_dist:
x,y = i,j
min_dist = dist[i][j]
if min_dist == INF:
#먹을 수 없는 물고기가 없는 경우
return None
else:
return x,y,min_dist #먹을 물고기의 위치와 최단 거리
최단거리 테이블이 주어졌을때 물고리를 찾는 함수를 만들었습니다.
x,y 위치는 0으로 최소거리는 INF로 초기화를 합시다.
그리고 2차원 테이블을 순회하기 위한 2중 for문을 만들었습니다. 최단거리 테이블에서 이동할 수 있는 경로를 모두 다른 숫자로 바뀌었습니다. 이제 -1은 못가는 곳으로 보아도 무방합니다.
그러니까 조건을 다시 살펴보면 이동이 가능한 곳이며(-1이 아니고) 먹이가 존재하고 (1이상) 그 먹이는 상어의 크기보다 작을때 (now_size보다 작은것) 먹을 수 있는 물고기가 됩니다.
여기서 조건에 다음과 같은 것이 있습니다.
거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기, 그러한 물고기가 여러마리라면, 가장 왼쪽에 있는 물고기를 먹는다. 테이블의 탐색은 왼쪽 위에서부터 순서대로 이루어집니다. 그러니 먹을 수있는 최초의 물고기는 자연스럽게 가장 왼쪽 위에 있는 물고기가 선택됩니다. 그리고 그 거리는 min_dist 최소 거리가 됩니다. 이제 물고기를 먹었으니 상어의 위치를 x,y로 업데이트를 하고 거리 역시 반영을 합시다.
그리고 길이가 새로 갱신되지 않았다면 물고기가 존재하지 않았다는 의미이니 None를 반환을 하고 그게 아니라면 상어의 위치(먹은 물고기)와 최단거리르 반환을 합니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
result = 0 #최종 답안
ate = 0 #현재 크기에서 먹은 양
while True:
#먹을 수 있는 물고기의 위치 찾기
value = find(bfs())
#먹을 수 있는 물고기가 없는 경우 현재까지의 거리 출력
if value==None:
print(result)
break
else:
#현재 위치 갱신 및 이동 거리 변경
now_x, now_y = value[0], value[1]
result += value[2]
#먹은 위치에는 이제 아무것도 없도록 처리
array[now_x][now_y] = 0
ate += 1
#자신의 현재 크기 이상으로 먹은 경우, 크기 증가
if ate >= now_size:
now_size += 1
ate = 0
이제 마지막 작동 코드를 살펴봅시다.
최종 답안과 현재 상어가 먹은 양을 체크하는 변수를 만들어둡니다.
첫번째로 먹을 수 있는 물고기를 탐색을 하고 value에는 상어의 위치와 최단 거리가 들어 있습니다. 그리고 그 값이 비어 있을때까지 출력을 합니다.
비어 있지 않다면 진행을 해봅시다 now_x, now_y는 현재 위치를 갱신을 하고 이동 거리를 result에 반영을 합니다. 그리고 이동한 위치에는 역시 물고기는 먹혔으니 0으로 고정을 하고 ate를 1추가를 합시다. 그리고 상어의 사이즈와 비교를 해서 현재 크기 이상으로 먹었을 경우 크기를 증가시키고 ate를 초기화를 시켜줍니다.
Comments powered by Disqus.