2022.05.17 [백준] (python 파이썬) 아기 상어
https://www.acmicpc.net/problem/16236
16236번: 아기 상어
N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가
www.acmicpc.net
풀이
이 문제는 BFS를 사용하면 되는 문제이지만 물고기를 먹을 때마다 BFS를 해야 한다.
이유는 물고기를 먹을때마다 다음에 먹을 물고기의 최단거리를 구해야 하기 때문이다.
우선
변수들을 선언해주었다.
이후 각 N*N크기의 데이터를 입력받았다.
이때 각 라인을 입력받을 때마다 해당 라인에 9가 있는지 확인했다. 만약 9가 있으면 shark_x, shark_y의 값을 해당 좌표로 저장했다. 입력을 모두 받고 다시 탐색하면 시간이 오래 걸릴거같아 입력받을 때마다 해당 라인을 확인했다.
또 입력받은 값이 0보다 크고 6보다 작거나 같으면 물고기가 있다는 말이기 때문에 fish_cnt를 증가시켰다.
BFS함수에서 방문여부를 체크할 vis배열을 선언후 deque에 현재 상어의 위치와 이동거리를 넣고 min_dis를 최대사이즈로 선언했다. 이유는 만약 탐색하다가 상어가 먹을 수 있는 물고기가 나오면 해당 물고기까지의 거리를 min_dis에 저장 후, min_dis보다 크면 덱에 추가하지 않기 위해서이다.
그리고 탐색을 하며 최단거리의 물고기를 찾고 fish_list에 좌표와 거리를 저장한다.
그리고 내림차순 정렬하여 가장 위에 있고 왼쪽에 있는 최단거리의 먹을 수 있는 물고기를 반환한다.
그리고 eat_cnt를 증가시키고 만약 shark_size와 eat_cnt가 같으면 shark_size를 증가시킨 후, eat_cnt를 0으로 초기화 시켜준다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
|
import sys
from collections import deque
N=int(input())
arr=[]
shark_x,shark_y=0,0 # 상어의 위치
shark_size=2 # 상어의 크기
eat_cnt=0 # 상어가 먹은 물고기 수
fish_cnt=0 # 물고기 수
time=0
dx=[0,0,1,-1]
dy=[1,-1,0,0]
for i in range(N):
arr.append(list(map(int,input().split())))
for j in range(N):
# 상어의 좌표 저장
if arr[i][j]==9:
shark_x,shark_y=i,j
arr[i][j]=0
#물고기의 갯수 카운팅
elif 0<arr[i][j]<=6:
fish_cnt+=1
def BFS(shark_x,shark_y):
vis = [[False for _ in range(N)] for _ in range(N)]
deq=deque()
deq.append([shark_x,shark_y,0])
vis[shark_x][shark_y]=True
#먹을 수 있는 물고기까지의 최단거리 저장할 변수
min_dis=sys.maxsize
#물고기의 좌표와 거리 저장
fish_list=[]
while deq:
x,y,dis=deq.popleft()
for i in range(4):
nx=x+dx[i]
ny=y+dy[i]
if 0<=nx<N and 0<=ny<N and not vis[nx][ny]:
#이동할 곳이 shark_size보다 작거나 같으면 이동할 수 있으므로
#해당 좌표의 vis배열 True로 변경
if arr[nx][ny]<=shark_size:
vis[nx][ny]=True
#이동한 곳이 0보다 크고 shark_size보다 작으면 먹을 수 있는
#물고기이므로 min_dis에 이동거리 저장
if 0<arr[nx][ny]<shark_size:
#이동거리가 min_dis보다 크면 최단거리가 아니기 때문에 pass
if min_dis>=dis+1:
min_dis=dis+1
#최단거리의 물고기 좌표, 거리 저장
fish_list.append((nx,ny,dis+1))
#이동할 좌표의 값이 0이고 이동거리가 min_dis보다 작으면 아직
#먹을 수 있는 물고기를 찾지 못했기 때문에 deq에 해당 좌표,거리 저장
if dis+1<min_dis:
deq.append([nx,ny,dis+1])
#만약 fish_list에 데이터가 들어있으면 최단거리에 먹을 수 있는
#물고기를 찾았기 때문에 해당 배열을 내림차순 정렬해준다.
#(내림차순 정렬하면 x좌표가 작은 순, 만약 같으면 y좌표가 작은순으로 저장됨)
#이때 이동거리는 모두 최단거리만 저장되어 따로 정렬에 영향을 끼치지 않음
if fish_list:
fish_list.sort()
print(fish_list)
#가장 위에 있고 가장 왼쪽에 있는 최단거리의 먹을 수 있는 물고기를 반환
return fish_list[0]
else:
return False
while fish_cnt:
result=BFS(shark_x,shark_y)
if not result:
break
shark_x,shark_y=result[0],result[1]
time+=result[2]
eat_cnt+=1
fish_cnt-=1
if shark_size==eat_cnt:
shark_size+=1
eat_cnt=0
arr[shark_x][shark_y]=0
print(time)
|
cs |