반응형
https://www.acmicpc.net/problem/10026
💡 적록색약
✅ 문제 풀이
- 골드 치고 쉬운 dfs 문제
- 보자마자 어떻게 풀어야 할지 접근방식이 바로 보이는 문제!!
- 주의해야 할 점은 적록색약일 경우 R,G가 인접해있으면 같은 영역으로 본다는 점
- 이런 영역 문제를 풀 때는 방문한 칸에 대해서는 방문 표시를 하기때문에, 두 가지 접근 방식에 대해서 서로 영향을 받지 않기 위해서 arr를 두개를 만들고 시작했다.
- arr1은 적록색약이 아닌 사람이 보는 영역으로, R은 1, G는2, B는3 을 저장했다.
- arr2는 적록색약인 사람이 보는 영역으로, R과 G는 1, B는 3을 저장했다. 이게 핵심이다. R과 G를 같은 값으로 배정하여 같은 영역으로 인식되도록 하였다.
- 방문한 것에 대해서는 arr 값을 0으로 갱신하도록 하며, 방문 여부를 체크했다.
- arr 크기만큼 순회하면서 각 칸이 0이 아니면 dfs 함수를 호출하여, 현재 위치와 현재 위치의 값, 그리고 참조할 arr를 인자로 넘겨주었다.
- arr1과 arr2에 대해서 각각 취해야 하기 때문에 두번 씩 호출해 주었다.
- dfs 함수 내 동작
- 현재 칸을 방문했으므로 값을 0으로 갱신해준다.
- 현재 칸을 기준으로 상하좌우가 arr의 범위내에 있고, 현재 칸과 값이 동일하면 같은 영역이므로 해당 칸에 대해서 DFS를 재귀호출하여 한 영역에 대해 계속 탐색하도록 하였다.
- 다시 돌아와서, main의 2중 for문에서 dfs가 호출되었다는 것은 영역의 시작과 같은 의미이므로, dfs를 호출한 후에는 answer을 증가시켜 영역을 개수를 카운트 하였다.
- 이때 적록색약이 아닌 경우는 answer1을, 적록색약인 경우는 answer2를 카운트 하도록 하였다.
- 최종 answer들을 출력한다.
✏ 코드 전문
#include<iostream>
#include<vector>
#include<string>
using namespace std;
int n;
vector<vector<int>> arr1;
vector<vector<int>> arr2;
int answer1 = 0;
int answer2 = 0;
int dx[] = { -1,1,0,0 };
int dy[] = { 0,0,-1,1 };
void dfs(int i, int j, int num, vector<vector<int>> &arr) {
arr[i][j] = 0;
for (int k = 0; k < 4; k++) {
int x = i + dx[k];
int y = j + dy[k];
if (x >= 0 && x < n&&y >= 0 && y < n&&arr[x][y] == num) {
dfs(x, y, num, arr);
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n;
arr1.resize(n, vector<int>(n));
arr2.resize(n, vector<int>(n));
string str;
for (int i = 0; i < n; i++) {
cin >> str;
for (int j = 0; j < n; j++) {
if (str[j] == 'R') {
arr1[i][j] = 1;
arr2[i][j] = 1;
}
else if (str[j] == 'G') {
arr1[i][j] = 2;
arr2[i][j] = 1;
}
else {
arr1[i][j] = 3;
arr2[i][j] = 3;
}
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (arr1[i][j] != 0) {
dfs(i, j, arr1[i][j], arr1);
answer1++;
}
if (arr2[i][j] != 0) {
dfs(i, j, arr2[i][j], arr2);
answer2++;
}
}
}
cout << answer1 << " " << answer2;
return 0;
}
반응형
'CO-TE > 백준' 카테고리의 다른 글
[백준] 9251번 C++ "LCS" 풀이 / DP (1) | 2024.01.31 |
---|---|
[백준] 7569번 C++ "토마토" 풀이 / bfs, 3차원 벡터 (1) | 2024.01.29 |
[백준] 2447번 C++ "별 찍기 -10" 풀이 / 재귀, 분할정복, 프렉탈 (0) | 2024.01.24 |
[백준] 11729번 C++ "하노이 탑 이동 순서" 풀이 / 재귀호출 (1) | 2024.01.23 |
[백준] 7576번 C++ "토마토" 풀이 / BFS, 너비우선탐색 (1) | 2024.01.22 |