[python] 17086. 아기 상어2

문제 출처

17086. 아기 상어

 

풀이

상어가 위치한 곳으로부터 가장 먼 곳의 거리를 구하는 문제이다. 특정 포인트로 부터 BFS로 8가지 방향으로 탐색했을때 가장 늦게 상어를 만나는 지점을 구하면 된다.

 

• 모든 배열을 탐색하며 상어가 존재하지 않는 빈 칸들의 위치를 배열(vacancies)에 담는다.
• 최대 안전거리를 구할 변수 max_를 초기화한다.
• vacancies로 while문을 돌리며 매번 요소 하나를 뽑아 빈 칸으로부터 상어가 존재하는 곳까지의 경로를 담을 큐(q) 배열에 넣는다.
• 상어가 존재하는 곳까지 BFS 탐색을 할때 방문한 곳을 표시할 배열(check)를 만들어 초기화한다.
• 탐색을 시작하는 초기 위치정보 q에서 뽑아 d, y, x 변수에 선언한다.
• 다음 좌표에 해당하는 위치정보를 q에 담을때 배열의 크기를 벗어나는 것과 이미 방문한 곳은 건너뛴다.
• 처음 방문하는 곳은 그곳까지의 이동거리와 좌표를 q에 담고 check에 표시해주고 다음 q로 넘어간다.
• 해당 좌표에 상어가 존재할때 d가 max_보다 크면 max_값을 바꿔주고 다음 빈 칸으로 넘어간다.
• 위 작업을 모든 빈칸에 똑같이 반복해 주면 최대 안전거리를 구한다.

 

N, M = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(N)]
vacancies = []

def get_vacancies():
    global vacancies
    for y in range(N):
        for x in range(M):
            if arr[y][x] == 0:
                vacancies.append((0, y, x))

def bfs():
    max_ = 0
    while vacancies:
        q = [vacancies.pop(0)]
        check = [[0]*M for _ in range(N)]
        while q:
            d, y, x = q.pop(0)
            if arr[y][x]:
                if d > max_:
                    max_ = d
                break

            for dx, dy in (0, -1), (1, -1), (1, 0), (1, 1), (0, 1), (-1, 1), (-1, 0), (-1, -1):
                nd, ny, nx = d+1, y+dy, x+dx
                if ny < 0 or ny >= N or nx < 0 or nx >= M:
                    continue
                if check[ny][nx]:
                    continue
                q.append((nd, ny, nx))
                check[ny][nx] = 1
    print(max_)

get_vacancies()
bfs()