10026번 백준 적록색약 C++(풀이)-(빡킹독님 코드 참고)

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

128 MB

32341

18698

14561

57.327%

문제

적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다.

크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록), B(파랑) 중 하나를 색칠한 그림이 있다. 그림은 몇 개의 구역으로 나뉘어져 있는데, 구역은 같은 색으로 이루어져 있다. 또, 같은 색상이 상하좌우로 인접해 있는 경우에 두 글자는 같은 구역에 속한다. (색상의 차이를 거의 느끼지 못하는 경우도 같은 색상이라 한다)

예를 들어, 그림이 아래와 같은 경우에

RRRBB
GGBBB
BBBRR
BBRRR
RRRRR

적록색약이 아닌 사람이 봤을 때 구역의 수는 총 4개이다. (빨강 2, 파랑 1, 초록 1) 하지만, 적록색약인 사람은 구역을 3개 볼 수 있다. (빨강-초록 2, 파랑 1)

그림이 입력으로 주어졌을 때, 적록색약인 사람이 봤을 때와 아닌 사람이 봤을 때 구역의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100)

둘째 줄부터 N개 줄에는 그림이 주어진다.

출력

 

적록색약이 아닌 사람이 봤을 때의 구역의 개수와 적록색약인 사람이 봤을 때의 구역의 수를 공백으로 구분해 출력한다.

예제 입력 1 복사

5
RRRBB
GGBBB
BBBRR
BBRRR
RRRRR

예제 출력 1 복사

4 3

---

접근법: 해당 문제의 경우 특별한 접근법은 없고, 정형화된 BFS를 구현할 줄 안다면,

1. 1차적으로 적록색인(순서는 상관없다) 사람의 경우: R-G를 구분하지 않기에, board 배열을 돌다가, R-G를 만나면, 동일한 BFS로 돌린다. 하지만, B를 만날 경우 R-G와의 조건이 다르기 때문에 새로운 BFS를 돌려줘야 한다. 

2. 2차적으로 일반인의 경우 R-B-G의 조건이 다 다르기 때문에, 3번의 다른 BFS을 구현했다. BFS 내부의 if 조건문만 다르기 때문에 사실상 복붙을 했다. 

#include<bits/stdc++.h>
using namespace std;
#define X first
#define Y second
string board[102];
bool vis[102][102];
int n;
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
int can_see, cant_see;
int main(void) {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n;
	for (int i = 0; i < n; i++) cin >> board[i];
	queue<pair<int, int>> q;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if ((board[i][j] == 'R'||board[i][j]=='G') && !vis[i][j]) {
				cant_see++;
				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 cx = cur.X + dx[dir];
						int cy = cur.Y + dy[dir];
						if (cx < 0 || cx >= n || cy < 0 || cy >= n)continue;
						if (board[cx][cy] == 'B' || vis[cx][cy])continue;
						vis[cx][cy] = 1;
						q.push({ cx,cy });
					}
				}
			}
			else if (board[i][j] == 'B' && !vis[i][j]) {
				cant_see++;
				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 cx = cur.X + dx[dir];
						int cy = cur.Y + dy[dir];
						if (cx < 0 || cx >= n || cy < 0 || cy >= n) continue;
						if(board[cx][cy]=='R'||board[cx][cy]=='G'||vis[cx][cy])continue;
						vis[cx][cy] = 1;
						q.push({ cx,cy });
					}
				}
			}
		}
	}
	for (int i = 0; i < n; i++)fill(vis[i], vis[i] + 100, 0);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (board[i][j] == 'R'&&!vis[i][j]) {
				can_see++;
				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 cx = cur.X + dx[dir];
						int cy = cur.Y + dy[dir];
						if (cx < 0 || cx >= n || cy < 0 || cy >= n) continue;
						if (board[cx][cy] == 'B' || board[cx][cy] == 'G' || vis[cx][cy])continue;
						vis[cx][cy] = 1;
						q.push({ cx,cy });
					}
				}
			}
			else if (board[i][j] == 'G' && !vis[i][j]) {
				can_see++;
				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 cx = cur.X + dx[dir];
						int cy = cur.Y + dy[dir];
						if (cx < 0 || cx >= n || cy < 0 || cy >= n) continue;
						if (board[cx][cy] == 'R' || board[cx][cy] == 'B' || vis[cx][cy])continue;
						vis[cx][cy] = 1;
						q.push({ cx,cy });
					}
				}
			}
			else if (board[i][j] == 'B' && !vis[i][j]) {
				can_see++;
				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 cx = cur.X + dx[dir];
						int cy = cur.Y + dy[dir];
						if (cx < 0 || cx >= n || cy < 0 || cy >= n) continue;
						if (board[cx][cy] == 'R' || board[cx][cy] == 'G' || vis[cx][cy])continue;
						vis[cx][cy] = 1;
						q.push({ cx,cy });
					}
				}
			}
		}
	}
	cout <<can_see<<" "<<cant_see;
}

단점: 코드 짜는 것은 어렵지 않지만, 길이 자체가 너무 길고, 실수의 여지가 너무 많다. 중간중간 확인하는 것이 좋으나, 애초에 가독성이 있는 코드를 짜는 것이 좋아보인다. (중복된 부분을 하나의 함수로 통일했으면 한다..... (함수의 목적)

---

빡킹독님 코드:

#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;
}

1. 갓킹독 그야 말로 깔끔한 코드가 아닐 수 없다. 따로 함수를 구현해 각각 중복된 BFS를 일일이 구현하는 것이 한 번만으로 해결해 가독성+짧은 코드 길이를 다 잡은셈이다! 

2. 무엇보다, if (vis[nx][ny] == 1 || board[i][j] != board[nx][ny]) continue; 해당 if조건을 통해, R,G,B 상관없이 개별적으로 다 돌 수 있다! =>생각하기 귀찮다고 일일히 다 구현하는 멍청한 짓을 하지 말자!!

3. 그렇다면, R-G 구분을 어떻게 했나? 했지만, 간단하게 board를 변경하면 되는 일!=> R-G를 구분하지 않는 것은 말 그대로 한 문자로 간주해도 됨으로 실제 board를 수정해 G=>R로 수정하면 아무 문제없다! 

4. 머리가 나쁘면 몸이 고생함..ㅠ 코드를 보다 간결화하는 방법들을 모색하고, 중복된 부분들을 일괄적으로 처리하는 방법을 모색하는 것이 중요하다!