백준 17086번 [아기 상어 2](C++) -yes6686- 티스토리

백준 문제 풀이: 17086 [아기 상어 2]

---

문제 링크: https://www.acmicpc.net/problem/17086

문제 설명:

해당 문제는 지도에서 아기 상어가 있는 위치로부터 가장 먼 안전 거리(아기 상어가 도달할 수 없는 최대 거리)를 계산하는 문제입니다. 지도에서 아기 상어는 값 1로 표시되며, 8방향으로 움직일 수 있습니다. 문제의 전체 설명과 예시는 위 링크를 참조하세요.

---

문제 해결 코드

#include <iostream>
#include <queue>
#include <cstring> // for memset
using namespace std;

const int dx[8] = { -1,-1,-1,0,0,1,1,1 }; // 8방향 (상, 하, 좌, 우 대각선)
const int dy[8] = { -1,0,1,-1,1,-1,0,1 };

int arr[51][51]; // 지도 배열
int dis[51][51]; // 거리 배열
queue<pair<int, int>> q;
int n, m; // 지도 크기

void bfs() {
    while (!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();

        for (int i = 0; i < 8; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue; // 범위 체크
            if (dis[nx][ny] > 0 || arr[nx][ny] == 1) continue; // 방문 여부 및 아기 상어 위치 체크

            dis[nx][ny] = dis[x][y] + 1; // 거리 갱신
            q.push({ nx, ny });
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> m;

    // 입력 처리 및 초기 아기 상어 위치 큐에 삽입
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> arr[i][j];
            if (arr[i][j] == 1) {
                q.push({ i, j }); // 아기 상어 위치를 큐에 삽입
            }
        }
    }

    bfs(); // BFS 수행

    int maxDistance = 0;
    // 최대 거리 계산
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            maxDistance = max(maxDistance, dis[i][j]);
        }
    }

    cout << maxDistance << '\n'; // 결과 출력
    return 0;
}

---

코드 설명

위 코드는 아기 상어가 있는 위치로부터 안전 거리를 계산하기 위해 BFS (너비 우선 탐색)을 활용한 풀이입니다. 주요 로직은 다음과 같습니다:

1. 초기화: 지도 크기와 데이터를 입력받으며, 아기 상어가 있는 위치를 큐에 삽입합니다.
2. BFS 수행: 큐에서 아기 상어 위치를 하나씩 꺼내고 8방향으로 이동하며 거리 배열을 업데이트합니다. 이미 방문했거나 아기 상어가 있는 칸은 건너뜁니다.
3. 최대 거리 계산: BFS 종료 후 거리 배열에서 가장 큰 값을 찾아 출력합니다.

해당 알고리즘은 BFS를 사용하여 모든 칸을 효율적으로 탐색하며, 시간 복잡도는 O(n * m)입니다.

---

결과

위 코드를 통해 문제를 정확히 해결할 수 있으며, BFS를 활용해 최적화된 풀이를 구현했습니다. 코드 최적화와 함께 주석을 추가해 가독성을 높였습니다. 개선 사항이나 질문이 있으면 댓글로 알려주세요!