2차원 배열이 주어졌을 때, 왼쪽 위 모서리에서 오른쪽 아래 모서리까지 도달할 수 있는 경로가 존재하는지 확인해야 합니다. 행렬은 0과 1로만 채워져 있으며, 0은 이동 가능한 열린 공간, 1은 막힌 구간(장애물)을 의미합니다. 단, 시작점인 왼쪽 위 칸은 항상 0이라고 가정합니다.
문제 예시
다음과 같은 5×5 행렬이 있다고 가정해 보겠습니다.
| 0 | 0 | 0 | 1 | 0 |
| 1 | 0 | 0 | 1 | 1 |
| 0 | 0 | 0 | 1 | 0 |
| 1 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 | 0 |
위 행렬에는 초록색으로 표시된 것처럼 여러 개의 유효한 경로가 존재합니다. 따라서 프로그램은 경로가 있으면 true, 없으면 false를 반환해야 합니다.
접근 방식: 도달 가능한 노드를 -1로 표시
이 문제는 접근 가능한 모든 노드의 값을 -1로 변경하는 방식으로 해결할 수 있습니다. 알고리즘의 동작 순서는 다음과 같습니다.
- 시작점인
arr[0][0]의 값을 -1로 설정합니다. - 첫 번째 열을 위에서 아래로 순회하며, 현재 값이 1(장애물)이 아니라면 바로 위 칸의 값을 그대로 물려받습니다.
- 첫 번째 행도 마찬가지로 왼쪽에서 오른쪽으로 순회하며, 장애물이 아니면 왼쪽 칸의 값을 전파합니다.
- 나머지 내부 영역에 대해서는 위쪽 칸과 왼쪽 칸의 값을 비교하여 최솟값을 현재 위치에 저장합니다. 만약 현재 위치가 1이라면 값은 변경하지 않습니다.
- 모든 순회가 끝난 후, 오른쪽 아래 끝 칸의 값이 -1이라면 경로가 존재하므로
true를 반환하고, 그렇지 않으면false를 반환합니다.
C++ 구현 코드
#include <iostream>
#define row 5
#define col 5
using namespace std;
bool isPathPresent(int arr[row][col]) {
arr[0][0] = -1;
for (int i = 1; i < row; i++)
if (arr[i][0] != 1)
arr[i][0] = arr[i - 1][0];
for (int j = 1; j < col; j++)
if (arr[0][j] != 1)
arr[0][j] = arr[0][j - 1];
for (int i = 1; i < row; i++)
for (int j = 1; j < col; j++)
if (arr[i][j] != 1)
arr[i][j] = min(arr[i][j - 1], arr[i - 1][j]);
return (arr[row - 1][col - 1] == -1);
}
int main() {
int arr[row][col] = {{ 0, 0, 0, 1, 0},
{1, 0, 0, 1, 1},
{ 0, 0, 0, 1, 0},
{1, 0, 0, 0, 0},
{ 0, 0, 1, 0, 0}};
if (isPathPresent(arr))
cout << "Path is present";
else
cout << "No path has found";
}실행 결과
Path is present
알고리즘 분석
이 방법은 사실상 동적 계획법(DP)의 원리를 활용한 것입니다. 각 칸은 왼쪽 또는 위쪽에서만 진입할 수 있다는 조건을 이용하여, 한 번의 순회로 모든 칸의 도달 가능 여부를 판별합니다.
- 시간 복잡도: O(row × col) — 행렬의 모든 칸을 정확히 한 번씩 방문합니다.
- 공간 복잡도: O(1) — 입력 배열 자체를 수정하여 별도의 추가 메모리를 사용하지 않습니다.
단, 이 방식은 이동이 오른쪽과 아래 방향으로만 가능하다는 제약이 있는 문제에 적합합니다. 상하좌우 네 방향 모두 이동이 허용되는 일반적인 미로 탐색 문제라면 BFS나 DFS를 사용하는 것이 더 적절합니다.