🧺입력
첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100)
둘째 줄부터 N개 줄에는 그림이 주어진다.
🧺출력
적록색약이 아닌 사람이 봤을 때의 구역의 개수와 적록색약인 사람이 봤을 때의 구역의 수를 공백으로 구분해 출력한다.
🔮예제 입력1
5 RRRBB GGBBB BBBRR BBRRR RRRRR
🔮예제 출력1
4 3
그래프이론, DFS, BFS
골드V
정말 간단한 문제였습니다.
저는 재귀함수사용하는 dfs연습중이라서 dfs로 풀었습니다.
몇가지만 알아두시면 되겠습니다.
- 적색맹은 빨간색, 초록색을 같다고 판단하면된다.
- dfs는 두개로 나눠서 하시면 매우 편하실겁니다.
#include <bits/stdc++.h>
constexpr int MAX = 101;
const int dx[4] = { 0, 0, 1, -1 };
const int dy[4] = { 1, -1, 0, 0 };
std::string adj[MAX];
bool visit[MAX][MAX];
void dfs1(int N, char c, int x, int y) {
visit[y][x] = true;
for (int i = 0; i < 4; ++i) {
int ny = y + dy[i];
int nx = x + dx[i];
if (nx >= 0 && ny >= 0 && nx < N && ny < N) {
if (!visit[ny][nx] && adj[ny][nx] == c) {
visit[ny][nx] = true;
dfs1(N, c, nx, ny);
}
}
}
}
void dfs2(int N, char c, int x, int y) {
visit[y][x] = true;
for (int i = 0; i < 4; ++i) {
int ny = y + dy[i];
int nx = x + dx[i];
if (nx >= 0 && ny >= 0 && nx < N && ny < N) {
if (!visit[ny][nx]) {
if (c != 'B') {
if (adj[ny][nx] == 'R' || adj[ny][nx] == 'G') {
visit[ny][nx] = true;
dfs2(N, c, nx, ny);
}
}
else {
if (adj[ny][nx] == c) {
visit[ny][nx] = true;
dfs2(N, c, nx, ny);
}
}
}
}
}
}
int main() {
std::cin.tie(0);
std::cout.tie(0);
std::ios_base::sync_with_stdio(0);
int N;
std::cin >> N;
for (int i = 0; i < N; ++i) std::cin >> adj[i];
int ColorBlindness = 0;
int Common = 0;
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
if (!visit[i][j]) {
dfs1(N, adj[i][j], j, i);
++Common;
}
}
}
for (int i = 0; i < N; ++i) for (int j = 0; j < N; ++j) visit[i][j] = false;
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
if (!visit[i][j]) {
dfs2(N, adj[i][j], j, i);
++ColorBlindness;
}
}
}
std::cout << Common << ' ' << ColorBlindness << '\n';
}
문제가 너무 쉬워서 바로 맞췄습니다.
저번에 풀던 실버dp문제가 더 어려웠던것같습니다.
확실히 백준은 문제유형에 따른 난이도배정 차이가 좀 큰듯합니다.
네트워크유량이나 강한결합요소같은거는 대부분 플래티넘이상인데 간혹가다가 실버dp문제보다 쉬운문제도 많이보이고 하니까..
궁금한 부분있으시면 댓글로 질문주세요~~