이 문제에서는 2차원 배열 mat[n][m]이 주어지며, 우리의 목표는 행렬에 존재하는 끝없는 지점(endless point)의 개수를 찾는 것입니다.
행렬의 어떤 지점이 끝없는 지점이 되려면, 해당 지점 자체가 1이고 그 뒤에 이어지는 모든 원소들이 1이어야 합니다. 즉, 아래 조건을 만족해야 합니다.
mat[i][j]가 끝없는 지점인 조건:
mat[i][j] == 1 이면서,
같은 행의 뒤 원소들(mat[i][j+1] … mat[i][m-1])과
같은 열의 아래 원소들(mat[i+1][j] … mat[n-1][j])이 모두 1
입력 예시
mat[][] = { {0, 0},
{1, 1} }출력
2
설명
두 번째 행의 mat[1][0]과 mat[1][1]이 끝없는 지점입니다. 두 원소 모두 값이 1이며, 그 뒤에 이어지는 행·열 방향의 원소들도 모두 1이므로 조건을 만족합니다.
단순 접근법
가장 직관적인 방법은 행렬의 모든 원소를 하나씩 순회하면서, 각 원소에 대해 그 뒤의 행과 열 원소들을 일일이 검사하는 것입니다. 조건을 만족하면 카운트를 증가시키고, 전체 탐색이 끝난 후 카운트를 반환합니다.
하지만 이 방법은 각 원소마다 최대 O(n + m)번의 검사가 필요하므로, 전체 시간 복잡도가 O(n × m × (n + m))까지 늘어날 수 있어 비효율적입니다.
효율적인 접근법: 동적 계획법(DP)
동적 계획법을 활용하면 훨씬 효율적으로 문제를 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- rowDP[i][j]: (i, j) 위치에서 시작하여 행 방향으로 연속된 1의 개수를 저장합니다. 값이 1이면
rowDP[i][j+1] + 1, 아니면 0입니다. - colDP[i][j]: (i, j) 위치에서 시작하여 열 방향으로 연속된 1의 개수를 저장합니다. 값이 1이면
colDP[i+1][j] + 1, 아니면 0입니다.
두 DP 테이블을 오른쪽·아래 방향부터 미리 계산해 두면, 각 위치가 끝없는 지점인지 O(1) 시간에 판별할 수 있습니다. 최종적으로 rowDP[i][j]와 colDP[i][j]가 모두 1 이상인 위치의 개수를 세면 정답이 됩니다.
구현 예제
#include <iostream>
using namespace std;
const int N = 2, M = 2;
int countEndlessPoints(bool mat[N][M]) {
int rowDP[N][M], colDP[N][M];
// 마지막 열과 마지막 행 초기화
for (int i = 0; i < N; i++)
rowDP[i][M-1] = mat[i][M-1];
for (int j = 0; j < M; j++)
colDP[N-1][j] = mat[N-1][j];
// 오른쪽에서 왼쪽으로 행 방향 DP 계산
for (int i = 0; i < N; i++)
for (int j = M-2; j >= 0; j--)
rowDP[i][j] = mat[i][j] ? rowDP[i][j+1] : 0;
// 아래에서 위로 열 방향 DP 계산
for (int j = 0; j < M; j++)
for (int i = N-2; i >= 0; i--)
colDP[i][j] = mat[i][j] ? colDP[i+1][j] : 0;
// 끝없는 지점 개수 집계
int count = 0;
for (int i = 0; i < N; i++)
for (int j = 0; j < M; j++)
if (rowDP[i][j] > 0 && colDP[i][j] > 0)
count++;
return count;
}
int main() {
bool mat[N][M] = { {0, 0}, {1, 1} };
cout << "끝없는 지점의 개수: " << countEndlessPoints(mat);
return 0;
}
출력
끝없는 지점의 개수: 2
복잡도 분석
- 시간 복잡도: O(n × m) — DP 테이블을 한 번씩 채우고 결과를 집계하기 때문입니다.
- 공간 복잡도: O(n × m) — 두 개의 보조 DP 테이블을 사용합니다.
이처럼 동적 계획법을 적용하면 단순 반복 검사 방식 대비 성능을 크게 향상시킬 수 있으며, 큰 크기의 행렬에서도 효율적으로 동작합니다.