문제 소개
0과 1로만 구성된 정사각형 행렬이 주어집니다. 여기서 0은 빈 칸(비어 있는 자리)을 의미하고, 1은 장애물을 나타냅니다. 우리의 목표는 빈 칸에 거울을 배치했을 때, 빛을 아래(bottom)에서 오른쪽(right)으로 전달할 수 있는 거울의 최대 개수를 구하는 것입니다.
거울이 특정 셀 [i, j]에 배치될 수 있는 조건은 다음과 같습니다.
- 같은 행(i)에서 해당 셀의 오른쪽에 있는 모든 셀에 장애물이 없어야 합니다.
- 같은 열(j)에서 해당 셀의 아래쪽에 있는 모든 셀에 장애물이 없어야 합니다.
즉, 거울이 A[i][j]에 있다면 A[i+1 ~ n][j]와 A[i][j+1 ~ n] 범위의 모든 값이 0(빈 칸)이어야 합니다. 아래 그림과 같습니다.
입력 및 출력 예시
입력
Arr[][] = {{0,0,1,0,0},{0,0,0,0,0},{0,0,0,0,0},{0,1,1,0,1},{1,1,1,0,1}}출력
거울의 개수 : 3
설명: 그림에서 볼 수 있듯이 거울은 다음 세 셀에 배치할 수 있습니다.
- Arr[1][0] — 1행 0열 기준으로 아래쪽과 오른쪽에 있는 모든 셀이 0입니다.
- Arr[2][0] — 2행 0열 기준으로 아래쪽과 오른쪽에 있는 모든 셀이 0입니다.
- Arr[4][4] — 마지막 셀로, 값이 0이며 아래쪽 행도 오른쪽 열도 존재하지 않으므로 조건을 만족합니다.
풀이 접근 방법
이 프로그램에서 사용한 접근 방식은 다음과 같습니다.
- 배열 Arr[][]는 0과 1로 이루어진 행렬을 나타냅니다.
- 함수 maximumMirror(int mat[][], int n)는 행렬과 그 크기 n을 입력받아, 위 조건을 만족하며 배치 가능한 거울의 최대 개수를 반환합니다.
- 변수 flag는 arr[i][j]의 아래쪽 또는 오른쪽 셀에 장애물이 존재하는지 표시하는 용도로 사용됩니다.
- 변수 count는 거울의 개수를 나타내며, 초기값은 0입니다.
- 행렬을 인덱스 (0,0)부터 순회(traverse)합니다.
- 각 셀이 비어 있으면(거울을 놓을 수 있는 후보) 먼저 아래쪽 셀들(k = i+1 ~ n-1)을 검사합니다. 이때 arr[k][j] 중 하나라도 장애물(값 1)이면 반복문을 종료하고 flag를 설정합니다. 장애물이 없다면 이어서 오른쪽 셀들(l = j+1 ~ n-1)을 검사합니다.
- 장애물이 발견되면 flag를 통해 표시합니다.
- 두 while 루프가 모두 끝난 후 flag가 0이면(장애물이 없으면) 해당 위치에 거울을 배치할 수 있으므로 count를 증가시킵니다.
- 모든 순회가 끝나면 count를 최대 거울 개수로 반환합니다.
C++ 구현 코드
// C++ program to find how many mirrors can transfer
// light from bottom to right
#include <bits/stdc++.h>
using namespace std;
// method returns number of mirror which can transfer
// light from bottom to right
int maximumMirror(int mat[5][5], int N){
// to mark that all cells in the right or bottom are 0---no obstacle
int flag=0;
int count=0; //count of mirrors
int i,j,k,l;
//for all cells
for (int i=0; i<N; i++)
for(j=0;j<N;j++){
//check from next column and next row
int k=i+1;
int l=j+1;
if(mat[i][j]==0) //position for mirror{
while(k<N) //check for rows below{
if(mat[k][j]==1) //keeping column fixed, if there is obstacle break{
flag=0; break; }
else
flag=1;
k++;
}
if(flag==1) //if no obstacle in rows then check columns in right
while(l<N) //checking for columns in right{
if(mat[i][l]==1) //keep row fixed, if obstacle break{
flag=0; break;
}
else
flag=1;
l++;
}
if(flag==1) //there is no obstacle for mirror mat[i][j]
count++;
}
}
return count;
}
int main(){
int N = 5;
//matrix where 1 represents obstacle form 5X5 matrix
int mat[5][5] = {{0,0,1,0,0},{0,0,0,0,0},{0,0,0,0,0},{0,1,1,0,1},{1,1,1,0,1}};
cout <<"Maximum mirrors which can transfer light from bottom to right :"<<
maximumMirror(mat, N) << endl;
return 0;
}실행 결과
Maximum mirrors which can transfer light from bottom to right :3
정리
이 문제는 각 빈 칸에 대해 같은 행의 오른쪽 방향과 같은 열의 아래쪽 방향을 차례로 검사하는 단순한 완전 탐색(brute-force) 방식으로 해결할 수 있습니다. 시간 복잡도는 O(N³)으로, 각 셀마다 최악의 경우 행과 열 전체를 확인해야 하기 때문입니다. 행렬 크기가 작다면 충분히 실용적인 접근 방법입니다.