C++ 그리드에서 열린 셀 간 최대 이동 횟수를 구하는 프로그램

h × w 크기의 그리드가 주어진다고 가정해 보겠습니다. 그리드의 각 셀은 두 가지 유형으로 구분됩니다. 접근할 수 없는 막힌 셀(blocked)과 자유롭게 이동할 수 있는 열린 셀(unblocked)입니다. 그리드는 2차원 배열로 표현하며, 막힌 셀은 '#'으로, 열린 셀은 '.'으로 나타냅니다.

목표는 한 열린 셀에서 출발해 다른 열린 셀에 도달할 때 필요한 이동 횟수의 최댓값을 구하는 것입니다. 이동은 상하좌우 방향(수직·수평)으로만 가능하고 대각선 이동은 허용되지 않으며, 경로에는 반드시 열린 셀만 포함되어야 합니다.

예를 들어 h = 4, w = 4이고 grid = {"..#.", "#.#.", "..##", "###."}라면 출력은 4입니다. 셀 (0, 0)에서 셀 (2, 0)까지 정확히 4번의 이동이 필요하기 때문입니다.

접근 방법: 너비 우선 탐색(BFS)

이 문제는 BFS(너비 우선 탐색)로 깔끔하게 해결할 수 있습니다. 그리드의 모든 열린 셀을 시작점으로 삼아 BFS를 수행하고, 각 시작점에서 도달할 수 있는 가장 먼 열린 셀까지의 거리를 계산한 뒤, 그중 최댓값을 답으로 반환합니다.

BFS는 같은 거리에 있는 셀들을 층층이 넓혀 가며 탐색하기 때문에, 어떤 셀에 처음 도달했을 때 기록된 dist 값이 곧 최단 거리가 됩니다. 따라서 각 시작점의 탐색 과정에서 기록된 최대 dist 값이 '그 시작점에서 가장 먼 열린 셀까지의 이동 횟수'를 의미합니다.

알고리즘 단계

상하좌우 이동을 위한 방향 배열 xdir = {1, 0, -1, 0}, ydir = {0, 1, 0, -1}을 정의합니다.
거리를 저장할 2차원 배열 dist와 초기화용 배열 reset을 준비하고, 결과 변수 res를 0으로 초기화합니다.
모든 셀 (i, j)를 순회하면서 해당 셀이 '.'이라면 dist[i][j]를 0으로 설정하고 좌표를 큐에 삽입합니다.
큐가 빌 때까지 맨 앞의 좌표 (x, y)를 꺼내고, res를 dist[x][y]와 비교해 더 큰 값으로 갱신합니다.
네 방향의 인접 좌표 (px, py)를 확인합니다. 좌표가 그리드 범위 안에 있고, 열린 셀이며, 아직 방문하지 않았다면(dist 값이 -1) dist 값을 1 증가시켜 저장하고 큐에 추가합니다.
모든 순회가 끝나면 res를 반환합니다.

C++ 구현 예제

#include <bits/stdc++.h>
using namespace std;

int solve(int h, int w, vector<string> grid){
    int xdir[4] = {1, 0, -1, 0};
    int ydir[4] = {0, 1, 0, -1};
    vector<vector<int>> dist(h, vector<int>(w, -1));
    vector<vector<int>> reset(h, vector<int>(w, -1));
    int res = 0;
    for(int i = 0; i < h; i++){
        for(int j = 0; j < w; j++){
            dist = reset;
            if(grid[i][j] == '.'){
                dist[i][j] = 0;
                queue<pair<int,int>> q;
                q.push(make_pair(i, j));
                while(!q.empty()){
                    int x = q.front().first;
                    int y = q.front().second;
                    res = max(dist[x][y], res);
                    q.pop();
                    for(int k = 0; k < 4; k++){
                        int px = x + xdir[k];
                        int py = y + ydir[k];
                        if(px >= 0 && px < h && py >= 0 && py < w){
                            if(grid[px][py] == '.'){
                                if(dist[px][py] == -1){
                                    dist[px][py] = dist[x][y] + 1;
                                    q.push(make_pair(px, py));
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    return res;
}

int main() {
    int h = 4, w = 4;
    vector<string> grid = {"..#.", "#.#.", "..##", "###."};
    cout << solve(h, w, grid);
    return 0;
}

입력

4, 4, {"..#.", "#.#.", "..##", "###."}

출력

복잡도 분석

모든 열린 셀마다 BFS를 한 번씩 수행하므로 전체 시간 복잡도는 O((h × w)²)입니다. 그리드가 커질수록 연산량이 제곱으로 늘어나므로, 큰 입력에서는 성능에 유의해야 합니다.