n × m 크기의 행렬이 있다고 가정해 보겠습니다. 각 셀에는 0부터 9 사이의 값 중 하나가 저장됩니다. 여기서 '깃발(flag)'은 줄무늬 형태여야 한다는 조건이 있습니다. 즉, 각 가로 행은 모두 같은 색상의 칸으로 이루어져야 하며, 인접한 두 가로 행은 서로 다른 색상이어야 합니다. 우리가 할 일은 주어진 행렬이 이러한 조건을 만족하는 유효한 깃발인지 검사하는 것입니다.
예를 들어 입력이 다음과 같다면,
| 0 | 0 | 0 |
| 1 | 1 | 1 |
| 3 | 3 | 3 |
첫 번째 행은 모두 0, 두 번째 행은 모두 1, 세 번째 행은 모두 3으로 구성되어 있고, 인접한 행들의 색상도 서로 다르므로 이 행렬은 유효한 깃발입니다.
풀이 접근 방식
이 문제는 다음 단계에 따라 해결할 수 있습니다.
- 행렬의 행 개수 n과 열 개수 m을 구합니다.
- 결과값 res를 1(true)로 초기화하고, 이전 행의 색상을 저장할 변수 l을 초기값으로 설정합니다.
- 각 행마다 해당 행의 첫 번째 값을 기준 색상 f로 삼습니다.
- 그 행의 모든 칸을 순회하면서 f와 다른 값이 하나라도 있으면 res를 0(false)으로 변경합니다.
- 현재 행의 색상 f가 바로 이전 행의 색상 l과 같다면 역시 res를 0으로 변경합니다.
- 모든 행을 검사한 후 res 값을 반환합니다.
n := 행렬의 행 개수
m := 행렬의 열 개수
l := 초기값('m')
res := 1
for i := 0 부터 n 미만까지, i를 1씩 증가시키며 반복:
f := matrix[i, 0]
for j := 0 부터 m 미만까지, j를 1씩 증가시키며 반복:
만약 matrix[i, j]가 f와 같지 않다면:
res := 0
만약 l이 f와 같다면:
res := 0
l := f
return (res가 0이 아니면 true, 그렇지 않으면 false)C++ 구현 예제
아래 구현 예제를 통해 더 자세히 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
bool solve(vector<vector<int>> matrix){
int n = matrix.size();
int m = matrix[0].size();
char l = 'm';
bool res = 1;
for (int i = 0; i < n; i++){
char f = matrix[i][0];
for (int j = 0; j < m; j++){
if (matrix[i][j] != f)
res = 0;
}
if (l == f)
res = 0;
l = f;
}
return res ? true : false;
}
int main(){
vector<vector<int>> matrix = { { 0, 0, 0 }, { 1, 1, 1 }, { 3, 3, 3 } };
cout << solve(matrix) << endl;
}입력
{ { 0, 0, 0 }, { 1, 1, 1 }, { 3, 3, 3 } }출력
1
코드 설명
이 알고리즘의 시간 복잡도는 행렬의 모든 칸을 한 번씩만 확인하므로 O(n × m)입니다. 변수 l은 이전 행의 색상을 추적하는 역할을 하며, 초기값 'm'은 실제 셀 값(0~9)과 절대 겹치지 않도록 설정된 임의의 문자입니다. 덕분에 첫 번째 행에서는 '이전 행과 색상이 같다'는 조건이 자동으로 통과됩니다. 만약 어떤 행이라도 내부적으로 색상이 섞여 있거나, 인접한 두 행의 색상이 동일하다면 res가 0으로 바뀌어 최종적으로 false가 반환됩니다.