C++로 그리드 목적지 도달 가능 여부 확인하는 방법

문제 소개

2개의 행과 n개의 열로 이루어진 그리드가 있다고 가정해 보겠습니다. 로봇은 그리드의 (0, 0) 위치에 있으며, 현재 위치에서 인접한 칸이나 대각선(모서리) 칸으로 이동하면서 (1, n - 1) 지점에 도달하려고 합니다.

그리드는 문자열 배열로 주어지며, 각 칸은 다음과 같이 표시됩니다.

• '#' : 막혀 있어 지나갈 수 없는 칸
• '.' : 자유롭게 이동할 수 있는 칸

우리가 확인해야 할 것은 로봇이 (0, 0)에서 출발하여 (1, n - 1) 칸에 도달할 수 있는지 여부입니다.

예를 들어, n = 4이고 grid = {".##.", "...."}인 경우 출력은 Possible(가능)이 됩니다.

해결 접근 방식

핵심 아이디어는 간단합니다. 로봇은 인접 칸 또는 대각선 칸으로만 이동할 수 있으므로, 어느 한 열의 두 칸이 모두 '#'으로 막혀 있다면 해당 열을 통과할 방법이 없습니다. 즉, 두 행 모두에서 같은 열이 막혀 있는 경우가 하나라도 존재하면 목적지에 도달할 수 없습니다.

이를 확인하는 알고리즘은 다음과 같습니다.

flag := 1
for initialize i := 0, when i < n, update (increase i by 1), do:
    if grid[0, i] is same as '#' and grid[1, i] is same as '#', then:
        flag := 0
if flag is same as 0, then:
    print("Not Possible.")
Otherwise
    print("Possible.")

C++ 구현 예제

아래 코드를 통해 실제 구현을 살펴보겠습니다.

#include <bits/stdc++.h>
using namespace std;
#define N 100
void solve(int n, string grid[]) {
    int flag = 1;
    for(int i = 0; i < n; i++){
        if(grid[0].at(i) == '#' && grid[1].at(i) == '#'){
            flag = 0;
        }
    }
    if (flag == 0)
        cout<<"Not Possible.";
    else
        cout<<"Possible.";
}
int main() {
    int n = 4;
    string grid[] = {".##.", "...."};
    solve(n, grid);
    return 0;
}

입력

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

출력

Possible.

코드 설명

solve 함수는 먼저 flag를 1로 초기화합니다. 이후 반복문을 통해 각 열(i번째 열)을 검사하면서, 첫 번째 행(grid[0])과 두 번째 행(grid[1])의 같은 열이 모두 '#'인지 확인합니다.

그런 열이 하나라도 발견되면 flag를 0으로 설정하고, 최종적으로 flag 값에 따라 결과를 출력합니다. 위 예제에서는 두 행 모두 막힌 열이 존재하지 않으므로 "Possible."이 출력됩니다.

이 알고리즘의 시간 복잡도는 O(n)으로, 그리드를 한 번만 순회하면 되기 때문에 매우 효율적입니다.