Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 풀어보는 '육지에서 최대한 멀리' 문제

문제 개요

N × N 크기의 격자(grid)가 주어지며, 각 칸은 0(물) 또는 1(육지)의 값만 가집니다. 이때 가장 가까운 육지 칸까지의 거리가 최대가 되는 물 칸을 찾아 그 거리를 반환해야 합니다.

거리는 맨해튼 거리(Manhattan distance)를 사용하며, 두 칸 (x0, y0)과 (x1, y1) 사이의 거리는 |x0 − x1| + |y0 − y1|로 계산합니다. 만약 격자에 육지만 있거나 물만 있다면 -1을 반환합니다.

101
000
101

예를 들어 위의 3×3 격자에서 출력값은 2입니다. 중앙에 있는 칸 (1, 1)이 네 모서리의 모든 육지로부터 정확히 거리 2만큼 떨어져 있어, 육지에서 가장 멀리 있는 물 칸이기 때문입니다.

접근 방법: 다중 출발점 BFS

이 문제는 다중 출발점 너비 우선 탐색(Multi-source BFS)으로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

  • 모든 육지 칸을 큐에 동시에 넣고 시작합니다.
  • BFS를 수행하며 바깥쪽으로 한 칸씩 확장할 때, 해당 물 칸이 어느 육지 칸에서 출발했는지를 맵(map)에 함께 기록합니다.
  • 탐색이 마지막으로 도달한 지점이 곧 육지에서 가장 먼 물 칸이며, 그때의 거리가 정답입니다.

알고리즘 단계

  • 4방향 이동 배열 정의: dir2 := [(1, 0), (-1, 0), (0, 1), (0, -1)]
  • 맵 m과 큐 q를 선언하고, n := 행 개수, c := 열 개수로 초기화합니다.
  • 격자를 순회하며 육지 칸 (i, j)를 모두 큐에 삽입하고, m[(i, j)] := (i, j)로 설정합니다.
  • 정답 변수 ret := -1로 초기화합니다.
  • 큐가 빌 때까지 다음을 반복합니다.
    • sz := 현재 큐의 크기
    • sz번 반복하며:
      • temp := 큐의 첫 번째 원소를 꺼내 제거
      • k를 0부터 3까지 반복하며:
        • nx := temp.first + dir2[k][0], ny := temp.second + dir2[k][1]
        • (nx, ny)가 격자 범위를 벗어나거나 이미 육지라면 다음 반복으로 건너뜁니다.
        • m[(nx, ny)] := m[temp] (출발 육지 좌표를 전파)
        • ret := max(calcDist((nx, ny), m[temp]), ret)
        • (nx, ny)를 큐에 삽입하고 grid[nx][ny] := 1로 방문 처리합니다.
  • 반복이 끝나면 ret을 반환합니다.

C++ 구현 예제

다음 구현을 통해 더 자세히 이해해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;
int dir2[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
class Solution {
    public:
    int calcDist(int x1, int y1, int x2, int y2){
        return abs(x1 - x2) + abs(y1 - y2);
    }
    int maxDistance(vector<vector<int>>& grid) {
        map < pair <int, int>, pair <int, int> > m;
        queue < pair <int, int> > q;
        int n = grid.size();
        int c = n? grid[0].size() : 0;
        for(int i = 0; i < n; i++){
            for(int j = 0; j < c; j++){
                if(grid[i][j] == 1){
                   q.push({i, j});
                   m[{i, j}] = {i, j};
                }
            }
        }
        int ret = -1;
        while(!q.empty()){
            int sz = q.size();
            while(sz--){
                pair <int, int> temp = q.front();
                q.pop();
                for(int k = 0; k < 4; k++){
                   int nx = temp.first + dir2[k][0];
                   int ny = temp.second + dir2[k][1];
                   if(nx < 0 || ny < 0 || nx >= n || ny >= c || grid[nx][ny]) continue;
                   m[{nx, ny}] = m[temp];
                   ret = max(calcDist(nx, ny, m[temp].first,
                   m[temp].second), ret);
                   q.push({nx, ny});
                   grid[nx][ny] = 1;
                }
            }
        }
        return ret;
    }
};
main(){
    vector<vector<int>> v1 = {{1,0,1},{0,0,0},{1,0,1}};
    Solution ob;
    cout << (ob.maxDistance(v1));
}

입력

{{1,0,1},{0,0,0},{1,0,1}}

출력

2

복잡도 분석

  • 시간 복잡도: O(n²) — 각 칸은 BFS 과정에서 최대 한 번씩만 방문됩니다.
  • 공간 복잡도: O(n²) — 큐와 출발 육지 좌표를 저장하는 맵이 격자 크기에 비례하여 사용됩니다.