득이공간
[백준 C++] 10026 적록색약 - 깊이우선탐색 본문
#include <iostream>
using namespace std;
int N;
char Color[100][100];
bool Visited[100][100];
bool Visited2[100][100];
int DX[4] = { -1, 0, 1, 0 };
int DY[4] = { 0, -1, 0, 1 };
void DFS(int X, int Y)
{
Visited[Y][X] = true;
for (int i = 0; i < 4; ++i)
{
int NX = X + DX[i];
int NY = Y + DY[i];
if (NX < 0 || NX > N - 1
|| NY < 0 || NY > N - 1
|| Visited[NY][NX]
|| Color[NY][NX] != Color[Y][X])
{
continue;
}
DFS(NX, NY);
}
}
void DFS2(int X, int Y)
{
Visited2[Y][X] = true;
for (int i = 0; i < 4; ++i)
{
int NX = X + DX[i];
int NY = Y + DY[i];
if (NX < 0 || NX > N - 1
|| NY < 0 || NY > N - 1
|| Visited2[NY][NX]
|| (Color[NY][NX] == 'R' && Color[Y][X] == 'B')
|| (Color[NY][NX] == 'G' && Color[Y][X] == 'B')
|| (Color[NY][NX] == 'B' && Color[Y][X] == 'R')
|| (Color[NY][NX] == 'B' && Color[Y][X] == 'G'))
{
continue;
}
DFS2(NX, NY);
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin >> N;
for (int i = 0; i < N; ++i)
{
for (int j = 0; j < N; ++j)
{
cin >> Color[i][j];
}
}
int Count = 0, Count2 = 0;
for (int i = 0; i < N; ++i)
{
for (int j = 0; j < N; ++j)
{
if (!Visited[i][j])
{
DFS(j, i);
++Count;
}
if (!Visited2[i][j])
{
DFS2(j, i);
++Count2;
}
}
}
cout << Count << ' ' << Count2;
}
깊이 우선 탐색을 이용해서 푸는 문제입니다.
적록색약인 사람이 보는 그림에 대한 탐색과
색약이 아닌 사람이 보는 그림에 대한 탐색을 나누어서
두 개의 DFS를 진행하도록 구현했습니다.
'PS > 알고리즘 문제풀이' 카테고리의 다른 글
[백준 C++] 16928 뱀과 사다리 게임 - 너비 우선 탐색 (0) | 2024.02.19 |
---|---|
[백준 C++] 14500 테트로미노 - 브루트포스 (0) | 2024.02.18 |
[백준 C++] 9019 DSLR - 너비우선탐색 (0) | 2024.02.18 |
[백준 C++] 7662 이중 우선순위 큐 - 우선순위큐 (0) | 2024.02.18 |
[백준 C++] 7569 토마토 - 너비우선탐색 (0) | 2024.02.17 |