[python] 백준 17086번: 아기 상어2(BFS)

# 17086 아기 상어2

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

17086번: 아기 상어 2

⭐ 코드

import sys
input = sys.stdin.readline

from collections import deque
N, M = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(N)]


# 상 우상 우 우하 하 좌하 좌 좌상
dx = [-1, -1, 0, 1, 1, 1, 0, -1]
dy = [0, 1, 1, 1, 0, -1, -1, -1]

def bfs(i,j):
    queue = deque()
    queue.append((i,j))
    visited = [[0] * M for _ in range(N)]
    visited[i][j] = 1 # 방문처리

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

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

            if 0 <= nx < N and 0 <= ny < M and visited[nx][ny] == 0:
                visited[nx][ny] = visited[x][y] + 1
                queue.append((nx, ny))

                if graph[nx][ny] == 1:
                    return visited[nx][ny]-1
    
result = []
for i in range(N):
    for j in range(M):
        if graph[i][j] == 0:
              result.append(bfs(i,j))

print(max(result))

📝 풀이

처음에 안전거리라는 말이 쉽게 와닿지 않았다. 문제에서 이야기하는 안전거리는 빈 공간에서부터 아기 상어가 있는 거리로, 0에서 1까지의 거리를 구하면 되는 문제이다.

 

처음에 접근했던 방법은 빈 공간(0)을 기준으로 탐색을 시작하고 아기상어(1)를 만나면 탐색을 중지하는 방식으로 접근했다. 그렇게 코드를 작성했더니 무슨 이유에서인지 20%까지 완료됐다가 틀렸다고 나왔다.

 

다음으로 접근한 방법은 주변 8칸을 돌면서 1이 나오지 않으면 visited에 1을 더해주고 만약에 1을 만나면 해당 칸의 visited의 값에서 1을 빼서 리턴시켜주는 방법으로 접근했다. 그리고 리턴한 값을 result 배열에 담아주고 result에 담긴 값들 중 가장 큰 값을 출력시켜주면 안전 거리의 최댓값이 되게 된다.

🔓 정답 코드 뜯어보기

import sys
input = sys.stdin.readline

from collections import deque
N, M = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(N)]


# 상 우상 우 우하 하 좌하 좌 좌상
dx = [-1, -1, 0, 1, 1, 1, 0, -1]
dy = [0, 1, 1, 1, 0, -1, -1, -1]

입력값 N, M과 graph를 생성해주고 8방향을 탐색하기 위한 방향설정을 해준다.

def bfs(i,j):
    queue = deque()
    queue.append((i,j))
    visited = [[0] * M for _ in range(N)]
    visited[i][j] = 1 # 방문처리

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

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

            if 0 <= nx < N and 0 <= ny < M and visited[nx][ny] == 0:
                visited[nx][ny] = visited[x][y] + 1
                queue.append((nx, ny))

                if graph[nx][ny] == 1:
                    return visited[nx][ny]-1

bfs 함수를 생성해주고 visited 리스트를 만들어준다. 초기 값은 0으로 설정하고 방문 했을시 1로 설정해준다. queue가 빌때까지 while문을 실행시켜주고 8방향 탐색한 nx, ny가 범위내에 있고 방문하지 않았던 곳이라면(visited[nx][ny] == 0) 이전 거리 (visited[x][y])에 1을 더한 값을 이동한 위치에 기록시켜준다. 

 

만약 이동한 위치에 1이 나올 경우 해당 칸의 visited[nx][ny] 배열 값에서 1을 빼서 리턴시켜준다.

result = []
for i in range(N):
    for j in range(M):
        if graph[i][j] == 0:
              result.append(bfs(i,j))
# result
# [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
print(max(result))

return 값을 담을 result 배열을 생성해주고 graph를 탐색하면서 0인 곳(안전거리)에서 bfs를 실행시켜주고 리턴값을 result에 담아준다. 최종적으로 모든 bfs가 실행되면 result에 담겨있는 값중에 최댓값이 안전 거리의 최댓값이 된다.