[백준] 17086번 아기 상어 2

아기 상어 2

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초	512 MB	13747	6805	5117	47.751%

문제

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

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

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

입력

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

출력

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

예제 입력 1

5 4
0 0 1 0
0 0 0 0
1 0 0 0
0 0 0 0
0 0 0 1

예제 출력 1

2

예제 입력 2

7 4
0 0 0 1
0 1 0 0
0 0 0 0
0 0 0 1
0 0 0 0
0 1 0 0
0 0 0 1

예제 출력 2

2

내 코드

틀렸습니다

from collections import deque

DIRECTIONS = [(-1, -1), (0, -1), (1, -1), (-1, 0), (1, 0), (-1, 1), (0, 1), (1, 1)]  # x, y 순서 ↖ 부터

def get_maximum_safety_distance(matrix, N, M):
    max_distance = 0

    for i in range(N):
        for j in range(M):
            if matrix[i][j] == 1:
                continue

            queue = deque([(j, i)])
            visited = [[False] * M for _ in range(N)]  # visited 초기화
            visited[i][j] = True
            this_distance = 1  # 1 거리부터 조사
            while_flag = False

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

                # 8방향 검사
                for dx, dy in DIRECTIONS:
                    nx, ny = x + dx, y + dy

                    # 8방향에 1이 있냐
                    if 0 <= nx < M and 0 <= ny < N and not visited[ny][nx]:
                        if matrix[ny][nx] == 0:
                            queue.append((nx, ny))
                            visited[ny][nx] = True
                        else:
                            max_distance = max(max_distance, this_distance)
                            while_flag = True
                            break

                if while_flag:
                    break

                # 8 방향 다 조사 후 1 증가
                this_distance += 1

    return max_distance

N, M = map(int, input().split())  # 세로 x 가로
matrix = [list(map(int, input().split())) for _ in range(N)]

print(get_maximum_safety_distance(matrix, N, M))

개선 코드

모든 거리 계산 후 max로 최대 거리 가져온다.

from collections import deque

DIRECTIONS = [(0, -1), (1, -1), (1, 0), (1, 1), (0, 1), (-1, 1), (-1, 0), (-1, -1)]  # 12시부터 시계방향

def get_maximum_safety_distance(N, M, matrix):
    queue = deque([])  # 아기 상어 위치 좌표 저장
    distances = [[-1] * M for _ in range(N)]

    # 아기 상어 위치 사전 파악해서 queue에 저장
    for y in range(N):
        for x in range(M):
            if matrix[y][x] == 1:
                queue.append((x, y))
                distances[y][x] = 0

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

        for dx, dy in DIRECTIONS:
            nx, ny = x + dx, y + dy

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

    return max([max(row) for row in distances])

N, M = map(int, input().split())  # 세로, 가로
matrix = [list(map(int, input().split())) for _ in range(N)]
print(get_maximum_safety_distance(N, M, matrix))

chatGPT

이 문제는 모든 빈 칸(0)에 대해 가장 가까운 아기 상어(1)와의 거리를 구하고, 그 중 최댓값을 찾는 문제입니다.

---

스스로 푼 풀이 (BFS)

1. 입력값을 받아서 2D 리스트(matrix)를 생성
2. BFS를 활용하여 거리 탐색
   • 모든 빈 칸(0)에서 BFS를 수행하여 가장 가까운 상어(1)까지의 거리를 구함
   • 8방향(대각선 포함)으로 이동 가능
3. 각 칸의 안전 거리 중 최댓값을 출력

이제 제시된 코드와 비교하여 더 나은 코드를 작성해보겠습니다.

---

제시된 코드의 문제점

• 모든 빈 칸(0)에서 BFS를 수행 → 시간 초과 가능성
  • 모든 (0, 0) ~ (N-1, M-1) 칸을 탐색하며 BFS를 수행하면, 최악의 경우 50×50×8×2500 = 50만 번 이상의 연산이 발생
• 상어(1)에서 BFS를 시작하면 더 효율적
  • *모든 1에서 동시에 시작하는 BFS (Multi-Source BFS)**를 사용하면 한 번의 탐색만으로 모든 칸의 안전 거리를 구할 수 있음.

---

개선된 코드 (Multi-Source BFS)

1. 초기 BFS 큐에 모든 상어(1)의 위치를 저장
2. 모든 상어(1)에서 동시에 BFS 시작
   • 각 빈 칸(0)의 최단 거리 갱신
   • 탐색이 끝나면 최댓값 출력

from collections import deque

# 8방향 이동 (대각선 포함)
DIRECTIONS = [(-1, -1), (0, -1), (1, -1), (-1, 0), (1, 0), (-1, 1), (0, 1), (1, 1)]

def get_max_safety_distance(N, M, matrix):
    queue = deque()
    distance = [[-1] * M for _ in range(N)]  # 거리 저장 배열 (-1: 방문 안 함)

    # 모든 상어(1)의 위치를 BFS 시작점으로 추가
    for i in range(N):
        for j in range(M):
            if matrix[i][j] == 1:
                queue.append((i, j))
                distance[i][j] = 0  # 상어가 있는 곳의 거리는 0

    max_distance = 0  # 안전 거리 최댓값

    # BFS 수행 (모든 상어에서 동시에 시작)
    while queue:
        x, y = queue.popleft()

        for dx, dy in DIRECTIONS:
            nx, ny = x + dx, y + dy

            # 범위 내에 있고, 아직 방문하지 않은 빈 칸(0)이면
            if 0 <= nx < N and 0 <= ny < M and distance[nx][ny] == -1:
                distance[nx][ny] = distance[x][y] + 1  # 거리 갱신
                max_distance = max(max_distance, distance[nx][ny])  # 최댓값 갱신
                queue.append((nx, ny))  # BFS 진행

    return max_distance

# 입력
N, M = map(int, input().split())
matrix = [list(map(int, input().split())) for _ in range(N)]

# 결과 출력
print(get_max_safety_distance(N, M, matrix))

---

왜 이 코드가 더 좋은가?

✅ 모든 빈 칸(0)에서 BFS를 반복 수행하는 대신, 한 번의 BFS만 실행

✅ O(NM)만큼만 탐색하므로 훨씬 빠름 (최대 2500번 탐색)

✅ Multi-Source BFS를 활용하여 자연스럽게 최단 거리 계산

---

시간 복잡도 분석

• 제시된 코드: O(NM × 8) ≈ O(8NM)
• 개선된 코드: O(NM) (모든 칸을 한 번만 방문)→ 최대 2500번 탐색으로 해결 가능!

---

결론

이 문제에서는 모든 상어에서 BFS를 동시에 시작하는 방식이 가장 효율적입니다.

즉, Multi-Source BFS를 활용하여 안전 거리를 구하는 것이 핵심! 🚀

부가 질문

첫 번째 예시에서 distance 배열의 최종 상태는?

최종 distance 배열은 다음과 같습니다:

2 1 0 1
1 1 1 1
0 1 2 2
1 1 1 1
2 2 1 0

이제 정확한 결과가 나왔습니다! 😊

내 생각

1. 상어(1) 에서 시작하는 방법으로 하면 더 쉽다.
2. visited 가 아니라 상어부터 거리를 저장하는 배열을 사용하면 된다.
3. 코드가 너무 복잡해질땐 다른 방법으로 다시 생각 해봐야겠다.