백준/ Gold 3 문제 , 백준 파이썬 16236 , 아기 상어 [BFS]

백준/ Gold 3 문제 , 백준 파이썬 16236 , 아기 상어

 

 

Check Point !   ( 해당사항 ✓체크 )

1. 막힘 없이 수월하게 풀린 문제인가?

2. 1시간이내로 풀렸던 문제인가?

3. 1시간 이상 or 며칠을 두고 풀어봤더니 풀린 문제인가?

4. 시간을 써도 도무지 풀 수 없는 문제인가?

5. 솔루션을 찾아봤는가?

-------------------------------------------------------------------------------------------
난이도 체감
1. 최상
2. 상
3. 중
4. 하


<이해도>
1. 완벽히 이해
2. 다소 헷갈리는 부분들이 있음
3. 이해 못함


<덧붙일 말>
주어진 규칙이 처음엔 조금 까다롭게 느껴졌다.

 

문제 출처

 

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

16236번: 아기 상어

 

 

풀이

 

 

 

1. 기본 세팅

 

처음 기본 세팅이다.

 

1. deque 선언

 

2. 상하좌우로만 이동할 수 있기 때문에 상하좌우 이동을 위한 vertical, parallel 세팅

 

3. 표를 저장할 ocean 선언

 

4. 값을 저장할 변수들 을 선언한다.

 

- 물고기 수

- 아기 상어의 위치를 저장할 변수(행 열)

- 아기 상어의 크기

- 걸린 시간

- 먹은 물고기의 수 

 

5. N의 입력을 받고 N x N 의 행렬을 입력 받는다.

 

이때, 한 행씩 입력 받으면서 물고기 수와, 아기상어의 초기 위치를 파악하기 위해 if 문을 사용한다.

 

 

2. BFS

 

다음은 BFS 이다.

 

dq에 초기값을 넣어준다. (아기 상어의 위치 x,y 와 현재 자신의 위치인 거리 0)

 

방문 유무를 체크하기 위해 N x N 의 visited 를 선언해주고 아기 상어의 위치는 방문 표시를 해준다.

 

 MIN 변수는 거리가 최소인 물고기의 위치를 찾기 위함인데, 초기 값은 최대한 큰 수로 설정해 준다.

 

이후 물고기들을 분류 하기 위해 담을 리스트를 선언 해준다. (fishInfo)

 

이후 초기값이 담긴 dq를 시작으로 dq 를 돌게 한다.

 

상하좌우로 이동하면서

 

다른 bfs 문제들과 동일하게 라인을 넘지 않는지 체크해주고 방문을 안한 곳들을 위주로 체크한다.

 

물고기가 존재하는 위치라면 확인해야 할 것이 있다.

 

물고기의 크기가 아기상어보다 큰가? 같은가? 작은가?

 

작다면? => MIN 값을 그 물고기와의 거리로 초기화 시켜주고 물고기정보 리스트에 담는다.

 

0의 자리이던가 물고기 크기가 작거나 같다면 이동할 수 있는 자리이므로  dq 에 담아준다.

 

 

while 문을 다 돌게 되면 물고기정보들이 담긴 리스트를 확인해 본다.

 

만약 물고기 정보가 담겨 있다면,

 

1. 거리순

2. 행 순

3. 열 순

 

으로 정렬하여 우선순위가 1순위인 값만 넘겨준다.

 

위와 같은 순서인 이유는

 

• 먹을 수 있는 물고기가 1마리보다 많다면, 거리가 가장 가까운 물고기를 먹으러 간다. => 거리순
  • 거리는 아기 상어가 있는 칸에서 물고기가 있는 칸으로 이동할 때, 지나야하는 칸의 개수의 최솟값이다.
  • 거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기, 그러한 물고기가 여러마리라면, 가장 왼쪽에 있는 물고기를 먹는다.  => 가장 위 (행 순), 가장 왼쪽 (열 순)

문제의 조건에 따라야 하기때문이다.

 

 

물고기 정보가 없다면 False를 리턴해준다.

 

 

 

 

 

3. BFS 호출 부분과 물고기를 먹고 아기상어의 몸집을 키우는 과정

 

 

우선 BFS는 물고기의 수만큼 호출해준다.

 

처리해줘야할 것들이 있다.

 

1. bfs 결과 값을 담을 변수 result

 

2. 만약 false 리턴시 더 먹을 물고기가 없다고 판단 => while 문 종료

 

3. 아기 상어의 새로운 위치를 저장해주고 다음 bfs 호출시에 전달

 

4. 물고기를 먹었다면 그 물고기를 먹기 위해 소요된 시간 +

 

5. bfs 를 한번 돌때마다 물고기 수 - , 먹은 숫자 +

 

6. 먹은 숫자가 아기 상어의 몸집과 같다면 몸집을 하나 키워준다. 먹은 수는 다시 초기화

 

 

 

마지막으로, 걸린 총 시간 출력.

 

 

 

 

 

정답

 

 

 

from collections import deque
import sys

vertical=[1,-1,0,0]
parallel=[0,0,1,-1]
N=int(input())
ocean=[]  # 리스트 저장
fish=0  # 물고기 수
x,y=0,0  # 아기 상어 위치
babyShark=2  # 아기 상어 크기
time=0  # 걸린 시간
eatCnt=0  # 먹은 물고기 수

for i in range(N):
    ocean.append(list(map(int,input().split())))
    for j in range(N):
        if ocean[i][j]!=0 and ocean[i][j]!=9:  # 물고기 수 카운트
            fish+=1
        elif ocean[i][j]==9:  # 처음 아기 상어 위치 저장
            x=i
            y=j
            ocean[i][j]=0  # 현재자리 빈곳으로 초기화

def bfs(x,y):
    dq=deque()
    dq.append([x,y,0]) 
    visited=[[False]*N for _ in range(N)]
    visited[x][y]=True
    MIN=sys.maxsize
    fishInfo=[]  #
    while dq:
        X,Y,dist=dq.popleft()
        for i in range(4):
            mx=X+vertical[i]
            my=Y+parallel[i]
            if 0<=mx<N and 0<=my<N and visited[mx][my]==False:  # 갈 수 있는 자리인지 확인
                if ocean[mx][my]<=babyShark:  #  아기상어 크기 이하인 물고기가 존재하는가?
                    visited[mx][my]=True
                    if 0<ocean[mx][my]<babyShark:  # 먹을 수 있는 물고기 인가?
                        MIN=dist
                        fishInfo.append((mx,my,dist+1))
                    if dist+1<=MIN:
                        dq.append([mx,my,dist+1])
    if fishInfo:
        fishInfo.sort(key=lambda x:(x[2],x[0],x[1]))  # 1. 거리순, 2. 행 순 3. 열 순
        return fishInfo[0]  # 첫번째 값만 리턴
    else:
        return False  # 물고기가 없을 시
    
while fish:
    result=bfs(x,y)
    if not result:
        break
    x,y=result[0],result[1]
    ocean[x][y]=0  # 잡아먹혔다 표시
    time+=result[2]  # 거리만큼 시간 증가
    fish-=1  # 물고기 수 감소
    eatCnt+=1  # 먹은 숫자 증가
    if babyShark==eatCnt:  # 아기상어 몸집과 먹은 수가 동일할 시 몸집+1
        babyShark+=1
        eatCnt=0
print(time)