[Silver II] 아기 상어 2 - 17086

문제 링크

성능 요약

메모리: 34332 KB, 시간: 140 ms

분류

너비 우선 탐색, 브루트포스 알고리즘, 그래프 이론, 그래프 탐색

문제 설명

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

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

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

입력

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

출력

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

---

풀이

아이디어

상어가 있는 칸을 기준으로 그래프의 값이 0인 부분이 나온다면 dep에 저장한다.
나올 수 있는 조건은 아래 3가지 인데

1. 해당 구역을 방문 안한 경우
2. 방문을 했고, 현재 상어보다 더 가까운 상어가 있는경우
3. 방문을 했고, 현재 상어가 더 가까운 경우

만약 현재 상어가 이전 상어보다 멀다면 그냥 지나고 가깝다면 해당 지역을 큐에 넣어 다시 탐색한다.

코드

import sys
from collections import deque
input = sys.stdin.readline
n, m = map(int, input().split())
g = [list(map(int, input().split())) for _ in range(n)]
v = [[0 for _ in range(m)] for __ in range(n)]
dep = [[0 for _ in range(m)] for __ in range(n)]

def bfs(x, y):
    q = deque([[x, y, 0]])
    dx = [-1, -1, 0, 1, 1, 1, 0, -1]
    dy = [0, 1, 1, 1, 0, -1, -1, -1]
    while q:
        cx, cy, d = q.popleft()
        for i in range(8):
            nx, ny = cx + dx[i], cy + dy[i]
            if (0 <= nx < n and 0 <= ny < m) and not g[nx][ny]:
                if v[nx][ny] == 0:
                    v[nx][ny] = 1
                    dep[nx][ny] = d+1
                    q.append([nx, ny, d+1])
                
                else:
                    if dep[nx][ny] <= d+1:
                        continue
                    else:
                        dep[nx][ny] = d+1
                        q.append([nx, ny, d+1])
                    
for i in range(len(g)):
    for j in range(len(g[i])):
        if g[i][j] == 1:
            bfs(i, j)

print(max(sum(dep, [])))

---

회고

쓸데없는 공간복잡도 최적화 해보겠다고 스스로 난이도 올려서 풀었던 문제..
굳이 쓸데없는짓 하지 말자..