https://www.acmicpc.net/problem/10026
10026번: 적록색약
적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록)
www.acmicpc.net

풀이 :
항상 느끼지만 백준 난이도는 좀 이상하다 실버 문제 못 풀때도 많은데 골드 문제라고 잔뜩 쫄아서 문제 읽어봤는데 그냥 BFS 두번 돌리면 되는거 아니야? 생각들어서 하나는 R과 G를 구분할 때 , 하나는 R과 G를 같은 색으로 취급할 때 이렇게 두개의 map을 만들어서 bfs함수를 두번돌렸더니 결과는 맞았다. 해결전략을 간단히 설명하면 주석에도 써놓았는데 R: 1, G: 2, B: 3 으로 생각했을 때 bfs로 탐색 시 현재 색깔을 저장해두고 방문하지 않은 노드 중에서 색깔이 같으면 방문하고 큐에 넣어주면 된다, RG를 구분 못할 경우에는 그냥 R과 G를 같은 숫자를 넣어주면 된다
#include <iostream> #include <queue> using namespace std; int map[101][101]; int map2[101][101]; int vis[101][101]; int n; queue<pair<int, int>> que; int dx[] = { 0,0,1,-1 }; int dy[] = { 1,-1,0,0 }; // R: 1, G: 2, B: 3 int RG = 0; int notRG = 0; void bfs(int a, int b) { int nowColor = map[a][b]; que.push({ a,b }); vis[a][b] = 1; while (!que.empty()) { pair<int, int> cur = que.front(); que.pop(); for (int i = 0; i < 4; i++) { int nx = cur.first + dx[i]; int ny = cur.second + dy[i]; if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue; if (vis[nx][ny] == 1 || map[nx][ny] != nowColor) continue; vis[nx][ny] = 1; que.push({ nx,ny }); } } } void bfs2(int a, int b) { int nowColor = map2[a][b]; que.push({ a,b }); vis[a][b] = 1; while (!que.empty()) { pair<int, int> cur = que.front(); que.pop(); for (int i = 0; i < 4; i++) { int nx = cur.first + dx[i]; int ny = cur.second + dy[i]; if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue; if (vis[nx][ny] == 1 || map2[nx][ny] != nowColor) continue; vis[nx][ny] = 1; que.push({ nx,ny }); } } } void initVis() { for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { vis[i][j] = 0; } } } int main() { ios::sync_with_stdio(0); cin.tie(0); cin >> n; string s; for (int i = 0; i < n; i++) { cin >> s; for (int j = 0; j < n; j++) { if (s[j] == 'R') { map[i][j] = 1; map2[i][j] = 1; } else if (s[j] == 'G') { map[i][j] = 2; map2[i][j] = 1; } else { map[i][j] = 3; map2[i][j] = 3; } } } for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (vis[i][j] == 0) { notRG++; bfs(i,j); } } } initVis(); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (vis[i][j] == 0) { RG++; bfs2(i, j); } } } cout << notRG << " "<< RG<<endl; }
간단하게 풀었지만 보다시피 코드가 쓸데없이 길고 중복이 많아서 나름 대로 줄여보았다! map2 사용하지 않고 vis 배열을 0으로 초기화 하면 map값을 바꿔서 그대로 bfs함수 재사용하는 방식!
#include <iostream> #include <queue> using namespace std; int map[101][101]; int vis[101][101]; int n; queue<pair<int, int>> que; int dx[] = { 0,0,1,-1 }; int dy[] = { 1,-1,0,0 }; // R: 1, G: 2, B: 3 int RG = 0; int notRG = 0; void bfs(int a, int b) { int nowColor = map[a][b]; que.push({ a,b }); vis[a][b] = 1; while (!que.empty()) { pair<int, int> cur = que.front(); que.pop(); for (int i = 0; i < 4; i++) { int nx = cur.first + dx[i]; int ny = cur.second + dy[i]; if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue; if (vis[nx][ny] == 1 || map[nx][ny] != nowColor) continue; vis[nx][ny] = 1; que.push({ nx,ny }); } } } int main() { ios::sync_with_stdio(0); cin.tie(0); cin >> n; string s; for (int i = 0; i < n; i++) { cin >> s; for (int j = 0; j < n; j++) { if (s[j] == 'R') { map[i][j] = 1; } else if (s[j] == 'G') { map[i][j] = 2; } else { map[i][j] = 3; } } } for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (vis[i][j] == 0) { notRG++; bfs(i,j); } } } for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { vis[i][j] = 0; if (map[i][j] == 2) map[i][j] = 1; } } for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (vis[i][j] == 0) { RG++; bfs(i, j); } } } cout << notRG << " "<< RG<<endl; }
'baekjoon' 카테고리의 다른 글
[DFS] 백준 2468 안전영역 C++ (0) | 2021.08.26 |
---|---|
[DP, DFS] 백준 1520 내리막길 C++ (0) | 2021.08.24 |
[DFS,BFS] 백준 2583 영역구하기 C++ (0) | 2021.08.16 |
[그리디] 백준 13305 주유소 C++ (0) | 2021.08.13 |
[그리디] 백준 1541 잃어버린 괄호 C++ (0) | 2021.08.13 |
댓글