백준 - 아기상어2 17086(Python)

[Silver II] 아기 상어 2 - 17086

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

문제설명

N×M 크기의 공간에 아기 상어 여러 마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 아기 상어가 최대 1마리 존재한다.

어떤 칸의 안전 거리는 그 칸과 가장 거리가 가까운 아기 상어와의 거리이다. 두 칸의 거리는 하나의 칸에서 다른 칸으로 가기 위해서 지나야 하는 칸의 수이고, 이동은 인접한 8방향(대각선 포함)이 가능하다.

안전 거리가 가장 큰 칸을 구해보자. 

 

입력

첫째 줄에 공간의 크기 N과 M(2 ≤ N, M ≤ 50)이 주어진다. 둘째 줄부터 N개의 줄에 공간의 상태가 주어지며, 0은 빈 칸, 1은 아기 상어가 있는 칸이다. 빈 칸과 상어의 수가 각각 한 개 이상인 입력만 주어진다.

 

출력

첫째 줄에 안전 거리의 최댓값을 출력한다.

 

 

예제입력 / 예제출력

 

문제이해 및 코드설명

주어진 맵에서 아기상어와 떨어진 거리의 최댓값을 구하는 문제이다.

문제를 풀기위해 상어에서부터 탐색을 시작하여 계산해나가는 접근법을 사용하였다.

이 문제는 bfs의 최단거리 구하기와 동일한 문제라고  생각할 수 있는데, 주의할점은 bfs에서 상하좌우 4방향만 취급하는 것과 달리 이 문제에선 대각선을 포함한 8칸의 이동까지 생각한다는 점이다.

 

문제를 풀면서 느낀점은, 이 문제처럼 상화좌우를 판단하여 탐색하면서 문제를 해결해야 할 경우, DFS나 BFS문제로 인식하는 경우가 많은것같다. 그래프의 모든 정점을방문하는 것이 주요한문제라면 2가지 방법모두 사용가능하고, 경로의 특징을 저장해야하는경우는 DFS의 방식을, 미로 찾기 또는 이 문제처럼 최단거리를 구해야하는경우에는 BFS가 유리하다. 왜냐하면 DFS에서는 처음으로 발견된다고 답이아니지만, BFS에서는 현재노드부터 가까운곳부터 찾기떄무네 탐색시 가장먼저 발견되는 곳이 곧 최단거리이기 떄문에 정답선택에 유리하다. 이 외에도 검색대상 그래프가 크다면 DFS , 규모가 크지않고 검색시작 지점으로 부터 원하는 대상이 별로 멀지 않다면 BFS도 고려해볼만하다고 한다.

문제에 따라 DFS,BFS를 골라서 잘 사용해야 할 듯하며, 이 부분은 많은 문제풀이를 통해 사용법을 익혀야겠다.

 

 

코드

import sys
from collections import deque


# bfs 탐색
def bfs():
    # 상/하/좌/우/대각선
    dx = [1, -1, 0, 0, 1, -1, 1, -1]
    dy = [0, 0, 1, -1, 1, -1, -1, 1]

    while queue:

        x, y = queue.popleft()

        # 상/하/좌/우/대각선 탐색
        for i in range(8):
            a = x + dx[i]
            b = y + dy[i]

            # 범위 내에 있고 탐색하지 않은 곳이라면 탐색
            if 0 <= a < n and 0 <= b < m:
                if visited[a][b] == 0:
                    # 탐색하기 까지 걸린 이동 횟수를 체크
                    visited[a][b] = visited[x][y] + 1
                    queue.append((a, b))


n, m = map(int, sys.stdin.readline().split())

# 상어가 있는 위치를 확인하고 그래프로 표현
visited = []
queue = deque()
for i in range(n):
    graph = list(map(int, sys.stdin.readline().split()))
    for j in range(m):
        if graph[j] == 1:
            queue.append((i, j))
    visited.append(graph)

bfs()

# 이동 거리에 최대 값을 구하고 처음 시작값을 뺀다.
dist = 0
for i in range(n):
    for j in range(m):
        dist = max(dist, visited[i][j])

print(dist - 1)