Algorithm
[BOJ] 10026번 : 적록색약
rudgh99_algo
2024. 8. 13. 23:45
1. problem :
https://www.acmicpc.net/problem/10026
2. solution 1 :
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
string board[102];
int vis[102][102];
int row,col; // row == col;
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
int normal_count;
int color_count;
queue<pair<int, int>> Q;
void bfs(int x, int y,char color) {
Q.push({ x,y });
vis[x][y] = 1;
while (!Q.empty()) {
pair<int, int> cur = Q.front(); Q.pop();
for (int dir = 0; dir < 4; dir++) {
int nx = cur.X + dx[dir];
int ny = cur.Y + dy[dir];
if (nx < 0 || nx >= row || ny < 0 || ny >= col) continue;
if (board[nx][ny] != color || vis[nx][ny] != 0) continue;
vis[nx][ny] = 1;
Q.push({ nx,ny });
}
}
}
void color_bfs(int x, int y, char color) {
Q.push({ x,y });
vis[x][y] = 1;
while (!Q.empty()) {
pair<int, int> cur = Q.front(); Q.pop();
for (int dir = 0; dir < 4; dir++) {
int nx = cur.X + dx[dir];
int ny = cur.Y + dy[dir];
if (nx < 0 || nx >= row || ny < 0 || ny >= col) continue;
if (board[nx][ny] == color || vis[nx][ny] != 0) continue;
vis[nx][ny] = 1;
Q.push({ nx,ny });
}
}
}
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> row;
col = row;
for (int i = 0; i < row; i++) cin >> board[i]; // board 채우기 ;
// 정상인부터 시작 Red --> Green --> Blue
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (board[i][j] != 'R' || vis[i][j]) continue;
normal_count++;
bfs(i, j, 'R');
}
}
// 정상인 Green 검사;
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (board[i][j] != 'G' || vis[i][j]) continue;
normal_count++;
bfs(i, j, 'G');
}
}
// 정상인 Blue 검사;
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (board[i][j] != 'B' || vis[i][j]) continue;
normal_count++;
bfs(i, j, 'B');
}
}
// vis 초기화;
for (int i = 0; i < row; i++) fill(vis[i], vis[i] + col, 0);
// 색맹 검사 ; Blue --> Red_Green; Blue
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (board[i][j] != 'B' || vis[i][j]) continue;
color_count++;
bfs(i, j, 'B');
}
}
// 색맹 검사 ; Red_Green;
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (board[i][j] == 'B' || vis[i][j]) continue;
color_count++;
color_bfs(i, j, 'B');
}
}
cout << normal_count << ' ' << color_count << '\n';
return 0;
}뭔가 코드를 줄일 수 있을 것 같다.
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
string board[102];
int vis[102][102];
int row,col; // row == col;
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
int normal_count;
int color_count;
char colors[3] = { 'R','G','B' };
queue<pair<int, int>> Q;
void bfs(int x, int y,char color) {
Q.push({ x,y });
vis[x][y] = 1;
while (!Q.empty()) {
pair<int, int> cur = Q.front(); Q.pop();
for (int dir = 0; dir < 4; dir++) {
int nx = cur.X + dx[dir];
int ny = cur.Y + dy[dir];
if (nx < 0 || nx >= row || ny < 0 || ny >= col) continue;
if (board[nx][ny] != color || vis[nx][ny] != 0) continue;
vis[nx][ny] = 1;
Q.push({ nx,ny });
}
}
}
void color_bfs(int x, int y, char color) {
Q.push({ x,y });
vis[x][y] = 1;
while (!Q.empty()) {
pair<int, int> cur = Q.front(); Q.pop();
for (int dir = 0; dir < 4; dir++) {
int nx = cur.X + dx[dir];
int ny = cur.Y + dy[dir];
if (nx < 0 || nx >= row || ny < 0 || ny >= col) continue;
if (board[nx][ny] == color || vis[nx][ny] != 0) continue;
vis[nx][ny] = 1;
Q.push({ nx,ny });
}
}
}
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> row;
col = row;
for (int i = 0; i < row; i++) cin >> board[i]; // board 채우기 ;
for (auto c : colors) {
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (board[i][j] != c || vis[i][j]) continue;
normal_count++;
bfs(i, j, c);
}
}
}
// vis 초기화;
for (int i = 0; i < row; i++) fill(vis[i], vis[i] + col, 0);
// 색맹 검사 ; Blue --> Red_Green; Blue
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (board[i][j] != 'B' || vis[i][j]) continue;
color_count++;
bfs(i, j, 'B');
}
}
// 색맹 검사 ; Red_Green;
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (board[i][j] == 'B' || vis[i][j]) continue;
color_count++;
color_bfs(i, j, 'B');
}
}
cout << normal_count << ' ' << color_count << '\n';
return 0;
}color라는 배열을 만들어서, 정상인의 for문을 1개로 축약했다.
3. solution 2 :
// Authored by : seeys
// Co-authored by : BaaaaaaaaaaarkingDog
// http://boj.kr/99a676d859f54fa0944f81f94ade04a3
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
char board[101][101];
bool vis[101][101];
int n;
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
void bfs(int i, int j) {
queue<pair<int, int>> Q;
Q.push({ i,j });
vis[i][j] = 1;
while (!Q.empty()) {
auto cur = Q.front(); Q.pop();
for (int dir = 0; dir < 4; dir++) {
int nx = cur.X + dx[dir];
int ny = cur.Y + dy[dir];
if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
if (vis[nx][ny] == 1 || board[i][j] != board[nx][ny]) continue;
vis[nx][ny] = 1;
Q.push({ nx,ny });
}
}
}
int area(){
int cnt = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (!vis[i][j]) {
cnt++;
bfs(i, j);
}
}
}
return cnt;
}
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> board[i][j];
}
}
int not_g = area(); //적록색약이 아닌사람
// 적록색약인 사람을 구하기위한 방문배열 초기화
for(int i = 0; i < n; i++)
fill(vis[i], vis[i]+n, false);
// 적록색약은 초록과 빨강을 구분 못하므로 초록이면 빨강으로 바꿔줌
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (board[i][j] == 'G')
board[i][j] = 'R';
}
}
int is_g = area(); //적록색약인 사람
cout << not_g << " " << is_g;
return 0;
}< source code 출처 : https://github.com/encrypted-def/basic-algo-lecture/blob/master/0x09/solutions/10026.cpp >
basic-algo-lecture/0x09/solutions/10026.cpp at master · encrypted-def/basic-algo-lecture
바킹독의 실전 알고리즘 강의 자료. Contribute to encrypted-def/basic-algo-lecture development by creating an account on GitHub.
github.com
이 코드는 정말 느끼는 게 많은 코드다. 내가 color_bfs를 따로 함수를 만든 이유는 R과 G를 또다시 로직을 짜기 위해서인데, G값을 R로 바꿔주면, 기존의 로직으로 작동하게 된다. 또, area라는 함수는 이중 loop를 돌면서 , 아직 방문하지 않은 원소면 bfs를 실행해 버린다. 나는 이 생각을 못해서 , red, green, blue일 때 세 가지의 경우의 수를 직접 작성했다. 그리고, bfs에서 color를 매개변수로 받지 않는 방법은 board [i][j]를 color로 쓰는 것이다. 마지막으로, input 이 들어왔을 때, 예를 들면, "RGBRGB"이때 배열을 char board [][] 형식으로 둘 수 있다는 것도 배운다.