이런 경우는 2에 경사로를 한 번 두면 더이상 경사로를 또 둘 수 없기 때문에 길이 될 수 없다.
이러한 경우들을 코드로 구현해보면
void Count(int arr[101][101]) {
for (int i = 1; i <= n; i++) {
int val = 0, cnt = 0;
//v 벡터에 한 줄 정보 표현
vector<pair<int, int> > v;
for (int j = 1; j <= n; j++) {
if (j == 1) {
val = arr[i][j];
cnt = 1;
continue;
}
if (arr[i][j] == val) {
cnt++;
}
else {
v.push_back({ val,cnt });
val = arr[i][j];
cnt = 1;
}
}
v.push_back({ val,cnt });
// 모두 같은 숫자인 경우
if (v.size() == 1) {
ans++;
continue;
}
//경사로 추가해서 길을 만들 수 있는지 확인
bool canmake = true;
for (int k = 0; k < v.size() - 1; k++) {
// 높이 차이가 1보다 크면 길이 될 수 없다.
if (abs(v[k].first - v[k + 1].first) > 1) {
canmake = false;
break;
}
if (v[k].first < v[k + 1].first) {
if (v[k].second < l) {
canmake = false;
break;
}
}
else {
if (v[k + 1].second < l) {
canmake = false;
break;
}
else {
// 332233 같은 경우를 위해 경사로를 두면 count에서 빼준다.
v[k + 1].second -= l;
}
}
}
if (canmake) ans++;
}
}
3.문제풀이코드 C++
#include <bits/stdc++.h>
using namespace std;
int n, l, arr[101][101], arr2[101][101], ans;
void Count(int arr[101][101]) {
for (int i = 1; i <= n; i++) {
int val = 0, cnt = 0;
vector<pair<int, int> > v;
for (int j = 1; j <= n; j++) {
if (j == 1) {
val = arr[i][j];
cnt = 1;
continue;
}
if (arr[i][j] == val) {
cnt++;
}
else {
v.push_back({ val,cnt });
val = arr[i][j];
cnt = 1;
}
}
v.push_back({ val,cnt });
if (v.size() == 1) {
ans++;
continue;
}
//경사로 추가해서 길을 만들 수 있는지 확인
bool canmake = true;
for (int k = 0; k < v.size() - 1; k++) {
if (abs(v[k].first - v[k + 1].first) > 1) {
canmake = false;
break;
}
if (v[k].first < v[k + 1].first) {
if (v[k].second < l) {
canmake = false;
break;
}
}
else {
if (v[k + 1].second < l) {
canmake = false;
break;
}
else {
v[k + 1].second -= l;
}
}
}
if (canmake) ans++;
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> l;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cin >> arr[i][j];
arr2[j][i] = arr[i][j];
}
}
Count(arr);
Count(arr2);
cout << ans << '\n';
return 0;
}
방문하지 않은 새로운 노드를 발견할 때마다 정답으로 출력할 변수에 +1을 해주면 구할 수 있습니다.
한번 더 나아가면 Union & Find 알고리즘을 이용해
서로 연결되어있는 노드는 같은 집합으로 분류해주고
부모노드의 개수를 세면 집합의 개수를 알 수 있습니다.
Union & Find 알고리즘을 이용하면 BFS나 DFS보다 시간을 절약해서 풀 수 있습니다.
3.문제풀이코드 C++
1. Union & Find C++
#include <bits/stdc++.h>
using namespace std;
int n, m , unf[1001], ans;
int Find(int a) {
if (a == unf[a]) {
return a;
}
else {
return unf[a] = Find(unf[a]);
}
}
void Union(int a, int b) {
a = Find(a);
b = Find(b);
if (a > b) {
swap(a, b);
}
if (a != b) {
unf[a] = b;
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
for (int i = 0; i <= 1000; i++) {
unf[i] = i;
}
for (int i = 0; i < m; i++) {
int a, b;
cin >> a >> b;
Union(a, b);
}
// 부모 노드의 개수 == 같은 집합의 개수
for (int i = 1; i <= n; i++) {
if (unf[i] == i) ans++;
}
cout << ans << '\n';
return 0;
}
11724 Union&Find
2. BFS
#include <bits/stdc++.h>
using namespace std;
int n, m;
bool ch[1001];
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
vector<int> map[1001];
for (int i = 0; i < m; i++) {
int a, b;
cin >> a >> b;
map[a].push_back(b);
map[b].push_back(a);
}
int ans = 0;
queue<int> Q;
for (int i = 1; i <= n; i++) {
if (!ch[i]) {
ans++;
ch[i] = 1;
Q.push(i);
while (!Q.empty()) {
int x = Q.front();
Q.pop();
for (int j = 0; j < map[x].size(); j++) {
if (ch[map[x][j]] == 0) {
ch[map[x][j]] = 1;
Q.push(map[x][j]);
}
}
}
}
}
cout << ans << '\n';
return 0;
}
