백준 - 16236번(BFS,구현)

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

16236번: 아기 상어

 

import sys
from collections import deque

n = int(sys.stdin.readline())

arr = []

for _ in range(n):
    arr.append(list(map(int,sys.stdin.readline().split())))

dx = [1,-1,0,0]
dy = [0,0,1,-1]
x = 0
y = 0
size = 2

for i in range(n):
    for j in range(n):
        if arr[i][j] == 9: #상어 시작 위치 파악
            x = i
            y = j
            break

def BFS(x,y,size):
    distance = [[0]*n for _ in range(n)] #도달하는 누적 거리
    visited = [[0]*n for _ in range(n)] #방문처리
    q = deque()
    q.append([x,y])
    visited[x][y] = 1
    tmp = deque([]) #현재 본인 사이즈보다 크기가 작은 애들의 위치, 누적거리 저장
    while q:
        x, y = q.popleft()

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            #arr의 범위를 벗어나지 않고 미방문한 경우
            if 0 <= nx < n and 0 <= ny < n and visited[nx][ny] == 0:
                if arr[nx][ny] <= size:
                    visited[nx][ny] = 1
                    distance[nx][ny] = distance[x][y] + 1
                    q.append([nx, ny])
                    #현재 사이즈보다 작은 물고기를 발견한 경우
                    if arr[nx][ny] < size and arr[nx][ny] != 0:
                        #해당 물고기의 좌표와 누적거리를 반환
                        tmp.append([nx,ny, distance[nx][ny]])

    return sorted(tmp,key=lambda x: (x[2],x[0],x[1]))
    #누적거리가 가장 작고, 가장 오른쪽, 가장 위에 있는 것이 우선순위


cnt = 0
r = 0
d = 0

while 1:
    shark = BFS(x,y,size) #BFS를 사용하기에 해당 물고기 까지 도달하는경우 최단거리임이 보장됨
    shark = deque(shark)


    if len(shark) == 0: #더 이상 먹을 수 있는 물고기가 없으면 반복문 탈출
        break

    nx,ny,d = shark.popleft() #가장 우선순위가 높은 물고기의 좌표, 누적거리
    r = r + d #누적거리 == 초 따라서 현재까지 값 더해주기

    arr[x][y], arr[nx][ny] = 0, 0 #시작지점 과 물고기 먹은 부분들은 0으로 초기화

    x,y = nx,ny #시작지점을 물고기를 먹고난 부분으로 변경
    cnt = cnt + 1 #해당 while문이 한번 실행될때마다 물고기를 1마리 먹은것과 같음
    if cnt == size:
        size = size + 1
        cnt = 0

print(r)

 

엄마에게 도움을 요청하지 않고 있을 수 있는 시간 == 최대한 짧은 시간 안에 먹을 수 있는 것들을 모두 먹는다. == 최대한 짧은 시간이란 최단 거리를 의미한다. == BFS 이렇게 생각을 했다.

다만 "아기 상어는 자신의 크기와 같은 수의 물고기를 먹을 때 마다 크기가 1 증가한다. 예를 들어, 크기가 2인 아기 상어는 물고기를 2마리 먹으면 크기가 3이 된다." 이 구문을 제대로 안읽어서 한참 헤맸다..

앞서 말한 조건이 하나 추가될 때마다 그래프 탐색 문제가 2배씩 어려워진다는 건 이런 의미도 있다..

 

큰 흐름은 다음과 같다.

1. 가장 우선순위가 높은 물고기까지 최단 거리 == 최소 시간에 도달해야 한다.

2. 더 이상 물고기를 먹지 못할 때까지 1의 조건을 만족하면서 1을 반복한다.

3. 최종적으로 1번의 누적시간을 모두 더해준다. 

 

arr을 탐색하다가 9가 되는 좌표를 시작 좌표로 설정해서 BFS를 호출한다.

상하좌우를 탐색해서 조건에 맞을 경우 q에 추가하고 누적거리를 더해주고, 방문처리를 한다.

자신보다 덩치가 작은 물고기를 만날 경우 tmp에 먹히는 물고기의 좌표, 시작 지점부터 해당 좌표까지의 누적거리를 삽입한다.

q에 더 이상 원소가 존재하지 않으면 tmp를 반환한다.

이때 중요한 부분이 있는데 정렬 후 반환을 해야한다. 왜냐하면 조건에 가까운 순으로, 위쪽과 왼쪽에 가까울 수록 우선 순위를 가진다고 했다. 해당 조건에 맞게 정렬후 반환을 해준다. 여기서 tmp를 큐로 만들면 기본 정렬이 오름차순이라서 나중에 popleft()로 꺼내면 돼서 편하다. 여기까지가 1번 과정이다.

 

while 반복문은 한번 반복될 때마다 시작 지점의 좌표가 바뀐다. 처음에는 arr [i][j] == 9 갇히는 상어의 위치(i, j)이고 그다음부터는 반환된 tmp에 의해 정의되는 shark의 조건 정렬에 의해 가장 최적 조건인 tmp [0] == shark [0] == shark.popleft() 좌표가 시작 좌표가 된다. BFS를 사용했기 때문에 tmp에 반환된 distance 즉 변수 d가 최단 거리라는 것을 보장할 수 있고 최단 거리는 최소 시간을 의미한다. 따라서 최종적으로 답이 될 r 변수에 d를 누적해서 더해주고 시작 지점과 시작 지점이 될 곳을 arr에서 0으로 초기화해준다. 또한 while문이 한번 실행이 되려면 물고기를 먹어야 하기 때문에 cnt를 1씩 증가시켜준다. 만약 cnt가 상어의 size와 동일해지면 조건에 따라 size를 1 증가시켜주고 cnt를 0으로 초기화시킨다.

 

BFS로부터 반환받는 tmp가 빈 리스트가 된다면 이는 전부 탐색을 했지만 조건에 맞는 케이스가 나오지 않은 것이므로 사실상 탐색이 끝난 것이다. 따라서 shark도 빈 리스트가 되기 때문에 빈 리스트가 되면 반복문을 종료하고 누적 값들의 합인 r을 출력해준다.