[C++] 아기 상어 2 (17086번)

아기 상어 2

문제

 

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

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

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

입력

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

 

---

문제풀이

접근 방법에 대해 고민을 조금 많이 했다. 우선 모든 아기 상어가 존재하는 좌표를 받아 벡터에 pair 쌍으로 저장해 주었다.

이후 모든 배열을 순회하면서 모든 아기상어의 위치와 비교해 안전거리가 몇인지 비교하였고, 이중 가장 작은 값을 해당 칸의 최대 안전거리로 설정하였다.

반복문을 세번 돌아야 해서 O(n*m*s)의 시간 복잡도가 나온다. 하지만 그 수가 크지 않기 때문에 충분히 시간 안에 처리가 가능하다고 생각했다. (n은 row, m 은 column, s는 아기 상어 개수)

 

1. 아기상어 좌표 저장

2. 각 칸 별로 최대 안전거리 구함

3. 최솟값 구함

 

#include <iostream>
#include <cmath>
#include <vector>

using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    int arr[n][m];
    vector<pair<int, int>> sharks;
    for(int i=0; i<n; i++) {
        for(int j=0; j<m; j++) {
            cin >> arr[i][j];
            // 상어 좌표 저장
            if(arr[i][j] == 1)
                sharks.push_back({i, j});
        }
    }

    int answer = 0;
    // 모든 칸 순회
    for(int i=0; i<n; i++) {
        for(int j=0; j<m; j++) {
        // 각 칸의 최소 안전거리
            int min_ = 99999999;
            for(int k=0; k<sharks.size(); k++) {
                int tmp = 0;
                int a = abs(sharks[k].first - i);
                int b = abs(sharks[k].second - j);
                if(a>0 && b>0) {
                    tmp += min(a, b);
                    tmp += abs(a-b);
                }
                else {
                    tmp += a + b;
                }
                if(min_ > tmp)
                    min_ = tmp;
            }
            // 최소 안전거리중 최댓값
            if(min_ > answer)
                answer = min_;
        }
    }

    cout << answer;
}

 

추가

 

문제를 풀고 나서 다른 사람들의 풀이를 찾아보았다. BFS 방식으로도 풀 수 있다. 아기 상어의 좌표를 큐에 넣고 인접 8칸의 값이 0일 경우 이전 값에 1을 더해주는 방식으로 한다면, 모든 칸의 최소 안전거리를 구할 수 있고 이 최소 안전거리 중 최댓값을 구할 수 있다.