제가 직접 경험해본 바로는, 백준 10026번 문제는 적록색약인 사람과 그렇지 않은 사람이 보이는 영역 수를 세는 문제입니다. BFS(너비 우선 탐색)를 이용하여 크기 N×N의 그리드에서 빨강, 초록, 파랑의 구역을 탐색하는 과정을 통해 문제를 해결할 수 있죠. 아래를 읽어보시면, 이 문제를 해결하는 방법에 대해 자세히 알아볼 수 있을 것입니다.
문제 이해 및 접근 방법
적록색약은 빨간색과 초록색의 차이를 인식하지 못합니다. 따라서 적록색약인 사람이 보는 그림은 그렇지 않은 사람과 다를 수 있습니다. 주어진 N × N 그리드에서 각 칸에 있는 색상이 R, G, B일 때, 각 사람별로 구역의 수를 세는 것이 문제의 핵심이지요. 이를 위해 다음과 같은 접근 방식을 취할 수 있습니다.
1. 그래프 구성
- 먼저 N×N 크기의 그래프를 구성합니다.
- 각 칸에는 R, G, B 중 하나의 색상이 저장됩니다.
- 적록색약인 사람을 위해 R과 G를 같은 색상으로 간주해야 합니다.
2. BFS를 통한 구역 탐색
- BFS를 통해 각 색상에 따라 구역을 탐색합니다.
- 일반인은 R, G, B를 명확히 구분하여 세 개의 영역으로 나눕니다.
- 적록색약인은 R과 G를 하나의 영역으로 보고 두 개의 영역(빨강과 파랑)으로 구분해 세어야 합니다.
위와 같은 접근 방식을 통해 문제를 해결하게 됩니다.
BFS 알고리즘 구현
이제 구현 단계로 넘어가겠습니다. BFS를 활용하여 서로 인접한 같은 색깔을 탐색하고 세는 로직을 작성할 수 있습니다. 아래는 그 구현 예시입니다.
코드에서 BFS 함수를 작성하고, 영역을 탐색하는 방법을 살펴보겠습니다.
코드 구현
“`cpp
include
include
include
include
using namespace std;
int dir[4][2] = { {0,1},{1,0},{0,-1},{-1,0} };
int n; // 그리드의 크기
void bfs(int row, int col, vector
char color = graph[row][col];
queue
q.push({ row, col });
graph[row][col] = ‘O’; // 방문한 칸 표시
while (!q.empty()) {
int r = q.front().first;
int c = q.front().second;
q.pop();
for (int i = 0; i < 4; i++) {
int next_r = r + dir[i][0];
int next_c = c + dir[i][1];
if (seq == 0 || color==’B’) { // 적록색약이 아니거나 색이 파랑일 때
if (next_r >= 0 && next_r < n && next_c >= 0 && next_c < n && graph[next_r][next_c] == color) {
q.push({ next_r, next_c });
graph[next_r][next_c] = ‘O’;
}
}
else { // 적록색약일 때
if (next_r >= 0 && next_r < n && next_c >= 0 && next_c < n && (graph[next_r][next_c] == ‘R’ || graph[next_r][next_c] == ‘G’)) {
q.push({ next_r, next_c });
graph[next_r][next_c] = ‘O’;
}
}
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n;
vector<vector<char>> graph(n, vector<char>(n));
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> graph[i][j];
}
}
int count;
for (int seq = 0; seq < 2; seq++) { // seq==0: 일반인, seq==1: 적록색약
vector<vector<char>> graph_copy(graph); // 그래프 복사
count = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (graph_copy[i][j] != 'O') { // 방문하지 않은 칸 찾기
bfs(i, j, graph_copy, seq);
count++;
}
}
}
cout << count << ' '; // 각 세며 나온 구역의 수 출력
}
return 0;
}
“`
코드 분석
bfs함수는 주어진 위치에서 시작해 인접한 같은 색상의 모든 칸을 탐색합니다.- 일반인일 경우와 적록색약일 경우를 나누어 색상을 비교하여 구역을 나누읍니다.
위의 코드를 통해 우리가 원하는 결과를 얻을 수 있습니다. BFS는 큐를 이용하여 탐색하는 만큼, 시간 복잡도도 효율적이지요.
출력 결과 검증
입력을 주어주면 적록색약이 아닌 사람과 적록색약인 사람의 구역 수를 출력하게 됩니다. 이러한 방법으로 문제를 해결할 수 있으니, 여러분도 직접 실행해 보시고 결과를 확인해보세요.
자주 묻는 질문 (FAQ)
BFS는 무엇인가요?
BFS(너비 우선 탐색)는 그래프 탐색 알고리즘으로, 시작 정점에서 접근 가능한 모든 정점을 탐색하는 방법입니다.
적록색약의 의미는 무엇인가요?
적록색약은 주로 빨강과 초록의 색을 구분하지 못하는 시각적 장애입니다.
이 문제를 해결할 때 주의할 점은 무엇인가요?
색상 비교할 때 적록색약인 경우 R과 G를 따로 구분하지 않고 한 범주로 묶어야 합니다.
코드에서 ‘O’는 어떤 의미인가요?
‘그림에서 해당 영역을 이미 탐색했음을 나타내기 위해 사용된 표시입니다.
이렇게 문제를 해결하고 나면, 일반인과 적록색약인 인물의 영역 수를 한 번에 이해할 수 있으니 실용적이지요. 여러 그래프 탐색 문제를 풀어보며 실력을 더욱 키워보시길 바랍니다.
키워드: 백준, BFS, 적록색약, 알고리즘, 그래프 탐색, C++, 문제 해결, 너비우선탐색, 영역 세기, 코드 문제, 그래프 구현