[백준] 17086 - 아기 상어 2

728x90

문제 링크

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

문제 요약

이 문제는 N×MN \times MN×M 크기의 격자(grid)가 있으며, 이 격자에는 여러 마리의 아기 상어가 있습니다. 각 칸은 빈 칸(0) 또는 아기 상어(1)를 나타냅니다. 이동은 8방향(상하좌우 및 대각선)으로 가능합니다.

각 칸의 안전 거리는 그 칸에서 가장 가까운 아기 상어까지의 최소 거리입니다. 목표는 모든 칸 중에서 안전 거리가 가장 큰 값을 찾아 출력하는 것입니다.

푼 방법

 

• 각 빈 칸에 대해 DFS 수행:
  • 빈 칸에서 시작하여 DFS를 통해 가장 가까운 아기 상어를 찾습니다.
  • DFS를 사용하여 모든 경로를 탐색하며, 아기 상어를 발견하면 현재까지의 이동 거리를 저장합니다.
• 안전 거리 계산:
  • 각 빈 칸마다 가장 가까운 아기 상어까지의 최소 거리를 계산합니다.
• 최대 안전 거리 갱신:
  • 모든 빈 칸에 대해 계산한 안전 거리 중에서 가장 큰 값을 찾습니다.

 

정답 코드

import math

n, m = list(map(int, input().split()))
space = []
for i in range(n):
    line = list(map(int, input().split()))
    space.append(line)

direction = [[-1,-1], [-1,0],[-1,1],[0,-1],[0,1],[1,-1],[1,0],[1,1]]

def move(y, x, visited, cnt):
    for d in direction:
        if y+d[0]<0 or y+d[0]>=n or x+d[1]<0 or x+d[1]>=m:
            continue
        if visited[y+d[0]][x+d[1]]:
            continue
        elif space[y+d[0]][x+d[1]] == 1:
            result.append(cnt+1)
            #print(cnt+1)
            return
        else:
            visited[y+d[0]][x+d[1]] = True
            # print(visited)
            move(y+d[0], x+d[1], visited, cnt+1)
            visited[y+d[0]][x+d[1]] = False

ans=math.inf

for i in range(n):
    for j in range(m):
        for k in direction:
            visited = [ [False for _ in range(m)] for _ in range(n)]
            result=[]
            visited[i][j]=True
            move(i, j, visited, 0)
            cnt=min(result)
            if ans > cnt:
                ans = cnt
        input()

print(ans)

배웠던 부분

 

• 이 코드는 DFS를 각 빈 칸마다 수행하기 때문에 시간 복잡도가 매우 높습니다. 격자의 크기가 최대 50이므로 최악의 경우 시간 초과가 발생할 수 있습니다.
• 효율적인 해결 방법:
  • 이 문제는 BFS(너비 우선 탐색)를 사용하여 해결하는 것이 더 효율적입니다.
  • 모든 아기 상어 위치에서 동시에 BFS를 시작하여 각 칸까지의 최소 거리를 계산할 수 있습니다.
  • 이렇게 하면 모든 칸에 대해 한 번의 BFS로 최소 거리를 계산할 수 있어 시간 복잡도를 크게 줄일 수 있습니다.