[Python] 16236.아기상어(골3) / 쉬운 풀이 : 구현+BFS탐색

목차

1. 문제

2. 핵심 아이디어

3. 코드

4. 배운 점

---

 

1. 문제

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

16236번: 아기 상어

---

2. 핵심 아이디어

2-1) 문제 조건 정리

- nxn의 격자판

- 각 턴마다 상화좌우 이동/ 이동시간은 1

 

 

- 통로 가능여부

=>자신과 몸무게가 같으면 -> 먹지는 못하고 통과는 가능

=> 자신보다 몸무게가 무거우면 -> 먹지도 못하고 통과도 불가

=> 자신보다 몸무게가 가벼우면 -> 먹어도 되며 통과도 가능

 

이동결정 과정

- 먹을 수 있는 물고기가 없다면 종료

- 먹을 수 있는 물고기가 한마리 => 그걸 먹자

- 먹을 수 있는 물고기가 여러마리

: 지나야하는 칸의 개수가 최소인 물고기를 먼저 먹음

: 거리가 같다면 가장 위/왼쪽 부터

 

-아기상어 크기

- 초기 아기상어 크기 : 2

자신의 크기와 같은 수의 물고기를 먹으면 1증가

ex) 크기가 3인 아기상어는 3마리 먹으면 4가 됨

 

출력값: 몇 초동안 아기상어가 물고기를 잡아먹을 수 있을까?

 

2-2) step by step

 

먼저 문제를 풀기 위해 아기상어의 입장을 생각해보자

 

아기상어는 다음 과정을 반복한다.

1. 자기보다 몸무게가 작은 아기상어의 위치를 모두 파악한다.

2. 이들에게 이를 수 있는 칸의 개수를 모두 계산해본다

3. 가장 최소인 물고기부터 먹으러 이동한다

 

그럼 백준 예제 2번으로 풀이 아이디어를 설명해보겠다.

격자판은 다음과 같다. (아기상어는 9 / 각 물고기 크기는 정수로 표시/ 0은 빈칸)

3
0 0 1
0 0 0
0 9 0

1-1) 아기상어 초기위치 잡기

우선 초기 아기상어의 위치가 주어지지 않기 때문에

격자판을 돌며 sx, sy에 아기상어의 초기 위치를 저장해주자

#격자판 정보
data= [list(map(int, input().split())) for _ in range(n)]

#아기상어 초기위치
for i in range(n):
  for j in range(n):
    if data[i][j]==9:
      sx=i
      sy=j

3
0 0 1
0 0 0
0 9 0

그럼 아기상어의 초기위치인 (2,1)이 (sx, sy)에 저장된다

 

1-2) 반복단계1

1. 자기보다 몸무게가 작은 아기상어의 위치를 모두 파악한다.

2. 이들에게 이를 수 있는 칸의 개수를 모두 계산해본다

3. 가장 최소인 물고기부터 먹으러 이동한다

 

격자판을 돌면서 먹을 수 있는 상어,

즉, 자신보다 몸무게가 적은 물고기들의 위치를

eatable 리스트에 담아주자

eatable=[]
    #먹을 수 있는 상어 고르기
    for i in range(n):
      for j in range(n):
      #격자판이 0이 아니고 아기상어보다 몸무게가 작으면 위치 담기
        if data[i][j] !=0 and data[i][j]<shark_size:
          eatable.append((i,j))

이 예제를 기준으로는 이런 결과가 나온다

(0,2)에 1kg 물고기가 있고 초기 상어의 몸무게인 2보다 작으므로

0 0 1
0 0 0
0 9 0

 

eatable = [(0,2)] 가 된다.

 

만약 먹을 수 있는 상어가 없으면 반복문은 종료될 것이다.

#먹을 수 있는 상어가 없다면 중지
    if len(eatable)==0:
      break

 

1-3) 반복단계2

1. 자기보다 몸무게가 작은 아기상어의 위치를 모두 파악한다.

2. 먹을 수 있는 물고기들에게 이르는 칸의 개수를 모두 계산해본다

3. 가장 최소인 물고기부터 먹으러 이동한다

 

거리를 파악하기 위해 BFS 탐색을 이용하기로 했다.

그 과정은 다음과 같다.

 

먼저 큐 안에 아기상어의 초기위치를 넣는다.

그리고 먹을 수 있는 상어들의 위치를 목적지로 둔다.

 

상하좌우로 탐색을 해나아가며

visited 2차원 배열을 갱신시킨다.

 

[data]              [visited]

0 0 1              -1  -1  -1
0 0 0              -1  -1  -1
0 9 0              -1   0  -1

 

초기 : 아기상어의 초기 위치를 0으로 갱신

 

bfs 탐색을 돌며 수행

 

1차

[data]              [visited]

0 0 1              -1  -1  -1
0 0 0              -1   1  -1
0 9 0               1   0   1

 

2차

[data]              [visited]

0 0 1              -1   2  -1
0 0 0               2   1   2
0 9 0               1   0   1

 

3차

[data]              [visited]

0 0 1               3   2   3
0 0 0               2   1   2
0 9 0               1   0   1

 

 

목적지에 도달했다.

(0,2)에 있는 물고기까지 아기상어는 3의 시간을 소비하여 갈 수 있다는 탐색결과가 나온다.

 

여기서 고려해주어야 하는 것은

1) 칸을 벗어나거나

2) 아기상어보다 몸무게가 큰 물고기가 있는 칸은 통과하지 못하기에

탐색을 종료해주어야 한다.

 

이를 코드로 옮긴 BFS 함수가 다음과 같다.

dx=[0,0,-1,1]
dy=[1,-1,0,0]

INF= sys.maxsize

def bfs(a,b,i2, j2): # a,b =>아기상어 초기위치 / i2, j2 => 목적지
  visited=[[-1]*n for _ in range(n)]
  visited[a][b]=0  #초기 아기상어 위치 0으로 갱신
  q=deque([(a,b)])

  while(q):
    x, y= q.popleft()

    for i in range(4): #상하좌우 탐색
      nx= x+dx[i]
      ny = y+dy[i]
		
      #격자판을 넘거나, 나보다 몸무게가 크면 건너뛰기
      if nx<0 or ny<0 or nx>=n or ny>=n or data[nx][ny]>shark_size:
        continue
      
      #만약 방문안했으면 지금거리+1로 갱신하고 q에 넣기 = bfs
      if visited[nx][ny] ==-1:
        visited[nx][ny]= visited[x][y]+1
        q.append((nx, ny))

  #만약 방문을 못했다면 큰수(INF)반환
  if visited[i2][j2]==-1:
    return INF
    
  #방문이 가능하면 그 시간을 반환
  else:
    return visited[i2][j2]

 

즉, 이 함수는 초기 아기상어 위치 a,b로부터

물고기의 위치 i2, j2까지의 최소거리를 반환하며

 

만약 가지 못할 경우 INF라는 큰 수를 반환하는 BFS 탐색함수이다.

 

그럼 이 함수를 이용하여 물고기들에게 이르는 거리를

eatable_route에 담아주자

eatable_route=[]

    #각 거리까지 구하기
    for a,b in eatable:
      k= bfs(sx,sy,a,b)
      if k!=INF:
        eatable_route.append((k, a,b))

    #먹을 수 있는 상어가 없다면
    if len(eatable_route)==0:
      break

앞선 data를 기준으로

[data]              

0 0 1               
0 0 0               
0 9 0    

 

아기상어의 초기위치 : (sx,sy) => 2,1

먹을 수 있는 물고기 위치  : a,b => 0,2

k= bfs(sx, sy, a,b) =>3

 

eatable_route= [(3,0,2)] 가 된다.

 

여기서 물고기의 위치를 같이 저장하는 이유는거리가 같으면 위/왼쪽이 우선순위 계산에 포함되기 때문이다.

 

 

따라서 eatable_route를 오름차순 정렬하면

eatable_route.sort()

거리 -> 행값 -> 열값순으로 우선순위가 계산되어 정렬되게 된다.

 

 

 

1-4) 반복단계3: 가장 가까운 물고기를 먹기

1. 자기보다 몸무게가 작은 아기상어의 위치를 모두 파악한다.

2. 이들에게 이를 수 있는 칸의 개수를 모두 계산해본다

3. 가장 가까운 물고기부터 먹으러 이동한다

 

이제 가장 가까운 물고기를 먹자

가장 가까운 물고기는 eatable_route[0]에 저장되어 있다.

 

eatable_route= [ (1순위 물고기 거리, 물고기 위치x, 물고기 위치y) , (2순위 물고기 거리............]

이런식으로 저장되어 있기 때문이다.

 

먼저 물고기까지 가는 시간을 time에 더하고

현재 상어가 있는 위치*(sx,sy)를 물고기가 있는 위치로 이동시켜준다.

	# 1순위 물고기 거리를 더함
    time+=eatable_route[0][0]
    
    #현재 아기상어 자리 바꾸기 => (sx,sy) <=>(1순위 물고기x, 1순위 물고기y)
    data[sx][sy]=0
    sx= eatable_route[0][1]
    sy= eatable_route[0][2]

 

이제 물고기가 커질 차례인지 보자

 

eat_cnt를 통해 먹은 물고기를 세고

만약 물고기 크기와 같아졌다면 물고기크기+1 / eat_cnt=0으로 초기화 하자

 

eat_cnt+=1
    if eat_cnt==shark_size:
      eat_cnt=0
      shark_size+=1

마지막으로 물고기를 먹은 현재 상어 위치를 상어의 크기로 갱신시켜주면 된다.

#sx,sy는 이동한 뒤에 상어 위치
data[sx][sy]=shark_size

 

 

이 과정을 하면 time 값에 결과가 담긴다.

 

전체코드를 바라보면...

---

3. 코드

from collections import deque
import sys
input= lambda: sys.stdin.readline().strip('\n')
INF= sys.maxsize

dx=[0,0,-1,1]
dy=[1,-1,0,0]

def bfs(a,b,i2, j2):
  visited=[[-1]*n for _ in range(n)]
  visited[a][b]=0  
  q=deque([(a,b)])

  while(q):
    x, y= q.popleft()

    for i in range(4):
      nx= x+dx[i]
      ny = y+dy[i]

      if nx<0 or ny<0 or nx>=n or ny>=n or data[nx][ny]>shark_size:
        continue
      
      if visited[nx][ny] ==-1:
        visited[nx][ny]= visited[x][y]+1
        q.append((nx, ny))

  
  if visited[i2][j2]==-1:
    return INF
  else:
    return visited[i2][j2]
  


n= int(input())

data= [list(map(int, input().split())) for _ in range(n)]
sx=0
sy=0
time=0

shark_size=2
eat_cnt=0

for i in range(n):
  for j in range(n):
    if data[i][j]==9:
      sx=i
      sy=j

while(1):
    eatable=[]
    #먹을 수 있는 상어 고르기
    for i in range(n):
      for j in range(n):
        if data[i][j] !=0 and data[i][j]<shark_size:
          eatable.append((i,j))

    #먹을 수 있는 상어가 없다면 중지
    if len(eatable)==0:
      break

    eatable_route=[]

    #각 거리까지 구하기
    for a,b in eatable:
      k= bfs(sx,sy,a,b)
      if k!=INF:
        eatable_route.append((k, a,b))

    #먹을 수 있는 상어가 없다면
    if len(eatable_route)==0:
      break

    eatable_route.sort()
    #print(eatable_route)
    
    #이동
    time+=eatable_route[0][0]
    data[sx][sy]=0
    sx= eatable_route[0][1]
    sy= eatable_route[0][2]
    eat_cnt+=1
    if eat_cnt==shark_size:
      eat_cnt=0
      shark_size+=1
    data[sx][sy]=shark_size

print(time)

---

4.배운점

 

격자판에서 상하좌우 움직이는 구현은 상당히 많이 나왔으나, 제한조건이 걸린 bfs와 연계되어

기능을 나누기가 쉽지 않았던 문제이다.

 

기능명세를 차근차근 나누고 하나씩 구현하다보면 전체가 구현되어 있는 모습이 너무 뿌듯했다.

divide and conquer의 매력을 느끼게 해준 문제