[16236] 아기상어 (2) _ bfs코드(진행중)

dx = (0, 0, 1, -1)
dy = (1, -1, 0, 0)

def bfs(shark_x, shark_y):
    q = collections.deque([(shark_x, shark_y, 0)])  #
    dist_list = []                                  #
    visited = [[False] * n for _ in range(n)]       #
    visited[shark_x][shark_y] = True                # 
    min_dist = inf                                  #
    while q:
        x, y, dist = q.popleft()
        for i in range(4):
            xx = dx[i] + x
            yy = dy[i] + y
            if 0 <= xx < n and 0 <= yy < n and not visited[xx][yy]:
                if board[xx][yy] <= shark_size:
                    visited[xx][yy] = True
                    if 0 < board[xx][yy] < shark_size:
                        min_dist = dist
                        dist_list.append((dist + 1, xx, yy))
                    if dist + 1 <= min_dist:
                        q.append((xx, yy, dist + 1))
    if dist_list: #dist_list가 비면 전체 로직이 멈추는 구조
        dist_list.sort()
        return dist_list[0]
    else:
        return False

 

1. 우선 짧게 BFS란 무엇인지 설명하자면,

 

Breadth-first search (BFS 너비 우선 탐색) 은 루트 노트(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법.

 

1)  deque / root node

 

선입선출인 queue를 변형한 형태로 좌, 우 상관없이 원할때에 입출력을 할 수 있는 큐다.

주목할 부분은, queue에서 (상어x,상어y,0)으로 root노드를 0부터 시작하게 세팅해놓았음을 확인할 수 있다.

 

2) dist_list 

 

deque로부터 popleft된 데이터들을 받아와서

 

 

3) visited 란

 

말 그대로, 상어가 움직인 지점은 또 가지 않기 위해 만들어놓은 장치, 아래 while 조건문에서 visited의 방문여부를 조건으로 걸어놓았음을 확인할 수 있다.

 

4)min_dist에 왜 infinite값이 들어갔는지

 

pass

 

5) while 구문 부분:

 

pass 

 

 

 

 

 

==========================================

전체 코드

import sys, collections
from math import inf

shark_x, shark_y = 0, 0
shark_size = 2
eat_count = 0

fish_count = 0
fish_position = []

time = 0

dx = (0, 0, 1, -1)
dy = (1, -1, 0, 0)

n = int(input())
board = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
#2차원 배열 입력받는 코드


#보드의 값을 수정하는
for i in range(n):
    for j in range(n):
        if 0 < board[i][j] <= 6: #물고기 수 및 위치 선정
            fish_count += 1
            fish_position.append((i, j))
        elif board[i][j] == 9:   #상어의 위치
            shark_x, shark_y = i, j #상어의 좌표를 데이터로 넘겨줌

board[shark_x][shark_y] = 0


def bfs(shark_x, shark_y):
    q = collections.deque([(shark_x, shark_y, 0)])
    dist_list = []
    visited = [[False] * n for _ in range(n)]
    visited[shark_x][shark_y] = True
    min_dist = inf
    while q:
        x, y, dist = q.popleft()
        for i in range(4):
            xx = dx[i] + x
            yy = dy[i] + y
            if 0 <= xx < n and 0 <= yy < n and not visited[xx][yy]:
                if board[xx][yy] <= shark_size:
                    visited[xx][yy] = True
                    if 0 < board[xx][yy] < shark_size:
                        min_dist = dist
                        dist_list.append((dist + 1, xx, yy))
                    if dist + 1 <= min_dist:
                        q.append((xx, yy, dist + 1))
    if dist_list: #dist_list가 비면 전체 로직이 멈추는 구조
        dist_list.sort()
        return dist_list[0]
    else:
        return False

while fish_count:
    result = bfs(shark_x, shark_y)
    if not result:
        break
    shark_x, shark_y = result[1], result[0]
    time += result[0]

    #fish count
    eat_count += 1
    fish_count -= 1

    if shark_size == eat_count:
        shark_size += 1
        eat_count = 0
    board[shark_x][shark_y] = 0

print(time)

 

 

 

 

출처 : https://gmlwjd9405.github.io/2018/08/15/algorithm-bfs.html

[알고리즘] 너비 우선 탐색(BFS)이란 - Heee's Development Blog