[C++로 풀이] 카카오 프렌즈 컬러링북 (BFS/DFS)⭐⭐
카테고리: Programmers
태그: Coding Test Algorithm
📌 카카오 프렌즈 컬러링북
난이도 ⭐⭐
🚀 문제
🚀 내 풀이
✈ 1 차 풀이 ❌
이 풀이는 틀린 풀이입니다.
#include <vector>
#include <algorithm>
vector<int> solution(int m, int n, vector<vector<int>> picture) {
vector<int> answer(2);
vector<vector<pair<int, int>>> record(picture.size()); // 모든 칸 마다 (칸, 속한 영역)
vector<int> group; // 영역마다 몇 칸 있는지
for (int i = 0; i < picture.size(); i++)
{
for (int j = 0; j < picture[i].size(); j++)
{
// 속한 영역 찾기
if (picture[i][j] == 0)
{
record[i].push_back(make_pair(picture[i][j], -1));
continue;
}
// 왼쪽, 위쪽 다 같은 영역인데 그룹을 합쳐야 할 때)
if (j >= 1 && i >= 1 && picture[i][j - 1] == picture[i][j] && picture[i - 1][j] == picture[i][j])
{
if (group[record[i][j - 1].second] < group[record[i - 1][j].second])
{
int groupIndex = record[i - 1][j].second;
record[i].push_back(make_pair(picture[i][j], groupIndex));
group[groupIndex]++;
int mustEraseGroupIndex = record[i][j - 1].second;
for (int k = 0; k <= j - 1; k++)
if (record[i][k].second == mustEraseGroupIndex)
record[i][k].second = groupIndex;
group[groupIndex] += group[mustEraseGroupIndex];
group.erase(group.begin() + mustEraseGroupIndex);
continue;
}
else if (group[record[i][j - 1].second] > group[record[i - 1][j].second])
{
int groupIndex = record[i][j - 1].second;
record[i].push_back(make_pair(picture[i][j], groupIndex));
group[groupIndex]++;
int mustEraseGroupIndex = record[i - 1][j].second;
for (int k = 0; k <= i - 1; k++)
if (record[k][j].second == mustEraseGroupIndex)
record[k][j].second = groupIndex;
group[groupIndex] += group[mustEraseGroupIndex];
group.erase(group.begin() + mustEraseGroupIndex);
continue;
}
else if (group[record[i][j - 1].second] == group[record[i - 1][j].second])
{
int groupIndex = record[i][j - 1].second;
record[i].push_back(make_pair(picture[i][j], groupIndex));
group[groupIndex]++;
int mustEraseGroupIndex = record[i - 1][j].second;
for (int k = 0; k <= i - 1; k++)
if (record[k][j].second == mustEraseGroupIndex)
record[k][j].second = groupIndex;
group[groupIndex] += group[mustEraseGroupIndex];
group.erase(group.begin() + mustEraseGroupIndex);
continue;
}
}
// 위쪽과 같은 영역일 때
if (i >= 1 && picture[i - 1][j] == picture[i][j])
{
int groupIndex = record[i - 1][j].second;
record[i].push_back(make_pair(picture[i][j], groupIndex));
group[groupIndex]++;
continue;
}
// 왼쪽과 같은 영역일 때
if (j >= 1 && picture[i][j - 1] == picture[i][j])
{
int groupIndex = record[i][j - 1].second;
record[i].push_back(make_pair(picture[i][j], groupIndex));
group[groupIndex]++;
continue;
}
// 속한 영역 없으면 새로운 영역
int groupIndex = group.size();
record[i].push_back(make_pair(picture[i][j], groupIndex));
group.push_back(1);
}
}
answer[0] = group.size();
answer[0] != 0 ? *max_element(group.begin(), group.end()) : 0;
return answer;
}
요새 코테를 3 달만에 풀어서인지 BFS, DFS를 다 까먹었다.. 그래서 이 문제를 그래프에 대응시키지 못했고 위와 같이 삽질하다가 포기..ㅠㅠ 힌트를 살짝 보려고 구글링 해보고나서야 이 문제가 BFS 문제라는 것을 알게 되어 BFS와 DFS를 복습한 후 아래와 같이 풀이했다!
✈ BFS 풀이 ⭕
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
vector<int> solution(int m, int n, vector<vector<int>> picture) {
vector<int> answer(2);
vector<vector<bool>> found(m, vector<bool>(n, false));
vector<int> colorCount; // 그래프별로 정점(=타일) 개수 저장
const int dirX[4] = { 0, -1, 0, 1 };
const int dirY[4] = { 1, 0, -1, 0 };
for (int i = 0; i < picture.size(); i++) {
for (int j = 0; j < picture[i].size(); j++) {
if (picture[i][j] == 0 || found[i][j] == true) continue;
// BFS 과정 (while문까지) : 처음으로 방문 안한 지역을 발견한다면 그건 새로운 그래프(=새로운 색 발견)라는 뜻이다. BFS 순회를 시작해야함.
int nowRow = i;
int nowCol = j;
queue<pair<int, int>> q;
q.push(make_pair(nowRow, nowCol));
found[nowRow][nowCol] = true;
colorCount.push_back(1); // 새로운 그래프 순회를 시작했으니 출발지 1개 추가
while (q.empty() == false) {
pair<int, int> pos = q.front();
nowRow = pos.first;
nowCol = pos.second;
q.pop();
for (int k = 0; k < 4; k++) {
int nextRow = nowRow + dirX[k];
int nextCol = nowCol + dirY[k];
if (nextRow < 0 || nextRow > m - 1 || nextCol < 0 || nextCol > n - 1) // 1. 그림을 벗어난 영역이 아니고
continue;
if (found[nextRow][nextCol] == true) // 2. 예약된 적이 없고
continue;
if (picture[nowRow][nowCol] != picture[nextRow][nextCol]) // 3. 색깔이 같다면 ! 이렇게 1,2,3 조건을 모두 만족하면 연결되어 있는 타일이니 추후 방문을 위해 큐에 예약!
continue;
q.push(make_pair(nextRow, nextCol));
found[nextRow][nextCol] = true;
colorCount.back()++; // 지금 순회중인 이 그래프는 colorCount에 최근에 뒤에 추가되었으니 가장 마지막 원소다. 예약했고 곧 방문 예정이니 타일 개수 1 더해줌.
}
}
}
}
answer[0] = colorCount.size();
answer[1] = *max_element(colorCount.begin(), colorCount.end());
return answer;
}
그래프에 대응시키기
- 예전에 배웠던 미로찾기처럼 타일 하나하나를 그래프 “정점”으로 생각하고, 같은 색깔 && 0 이 아닌 곳이라 갈 수 있는 곳이라면 “간선”으로 연결되어있는 정점이라고 생각하면 된다. 이렇게 그래프에 대응시킬 수 있다면 그래프를 순회하는 문제로 생각해볼 수 있을 것이다.
- 연결 되어 있는 모든 정점 순회 👉
DFS,BFS- 연결 되어 있다고 판단되는 기준
0이 아닌 곳- 나(정점)와 같은 색깔 (pictrue 원소 값이 같을 때)
- 나(정점)의 상하좌우에 있을 때
- 연결 되어 있다고 판단되는 기준
BFS
예제에선 그림이 12개 영역으로 나뉘어져 있다고 했는데 이는 그래프가 독립적으로 12개 있는 것이나 마찬가지이다. 같은 색깔이고 상하좌우에 있는 것들끼리가 같은 그래프라고 생각할 수 있다. 색깔이 다른 타일은 서로 다른 그래프라 연결되어 있지 않다고 볼 수 있다.
이중 for문 내에서 BFS를 진행하는 이유는, 이러한 각각의 그래프별로 BFS 를 진행하기 위해서이다. 그래프가 하나가 아니기 때문이다! 어피치 얼굴 색이 되는 분홍색 타일들을 큐를 사용해 BFS로 모두 순회했다면 분홍색 그래프 하나를 전부 순회한 것이나 마찬가지이니 이 분홍 타일들은 전부 방문 체크가 되어 있을 것이다. 다음 for문 반복에서 처음으로 방문이 안된 색깔을 발견하면 이제 그 타일은 새로운 그래프에 속한 정점인 것이니 새롭게 그 타일을 시작점으로 큐를 생성해서 BFS로 또 그 새로운 그래프를 순회하고 이런 식이다! 위의 코드로 보자면 큐가 이중 for문 도는동안 총 12번 만들어졌고 BFS가 12번 실행되었을 것임을 알 수 있다!
아래 과정을 큐가 비어있을 때까지(= 하나의 그래프 순회를 완료할 때까지) 반복한다.
- 큐에서 꺼내서 방문한다.
while (q.empty() == false) { pair<int, int> pos = q.front(); nowRow = pos.first; nowCol = pos.second; q.pop(); - 연결되어 있는 정점을 검사한 후 통과하면 큐에 삽입하여 예약
for (int k = 0; k < 4; k++) { int nextRow = nowRow + dirX[k]; int nextCol = nowCol + dirY[k]; if (nextRow < 0 || nextRow > m - 1 || nextCol < 0 || nextCol > n - 1) // 1. 그림을 벗어난 영역이 아니고 continue; if (found[nextRow][nextCol] == true) // 2. 예약된 적이 없고 continue; if (picture[nowRow][nowCol] != picture[nextRow][nextCol]) // 3. 색깔이 같다면 ! 이렇게 1,2,3 조건을 모두 만족하면 연결되어 있는 타일이니 추후 방문을 위해 큐에 예약! continue; q.push(make_pair(nextRow, nextCol)); found[nextRow][nextCol] = true; colorCount.back()++; // 지금 순회중인 이 그래프는 colorCount에 최근에 뒤에 추가되었으니 가장 마지막 원소다. 예약했고 곧 방문 예정이니 타일 개수 1 더해줌. }
✈ DFS 풀이 ⭕
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
int DFS (vector<vector<int>>& picture, vector<vector<bool>>& found, int& m, int& n, int& color, int row, int col){
int count = 1; // DFS가 진행되는 동안 타일 개수를 하나씩 센다.
found[row][col] = true;
// 위 쪽이 연결되어 있는지 검사하고 연결되어 있다면 깊이 들어감.
if (row - 1 >= 0)
if(picture[row - 1][col] == color)
if(found[row - 1][col] == false)
count += DFS(picture, found, m, n, color, row - 1, col);
// 아래 쪽이 연결되어 있는지 검사하고 연결되어 있다면 깊이 들어감.
if (row + 1 < m)
if(picture[row + 1][col] == color)
if(found[row + 1][col] == false)
count += DFS(picture, found, m, n, color, row + 1, col);
// 왼 쪽이 연결되어 있는지 검사하고 연결되어 있다면 깊이 들어감.
if (col - 1 >= 0)
if(picture[row][col - 1] == color)
if(found[row][col - 1] == false)
count += DFS(picture, found, m, n, color, row, col - 1);
// 오른 쪽이 연결되어 있는지 검사하고 연결되어 있다면 깊이 들어감.
if (col + 1 < n)
if(picture[row][col + 1] == color)
if(found[row][col + 1] == false)
count += DFS(picture, found, m, n, color, row, col + 1);
return count;
}
vector<int> solution(int m, int n, vector<vector<int>> picture) {
vector<int> answer(2);
vector<vector<bool>> found(m, vector<bool>(n, false));
vector<int> colorCount;
for (int i = 0; i < picture.size(); i++) {
for (int j = 0; j < picture[i].size(); j++) {
if (picture[i][j] == 0 || found[i][j] == true) continue;
colorCount.push_back(DFS(picture, found, m, n, picture[i][j], i, j));
}
}
answer[0] = colorCount.size();
answer[1] = *max_element(colorCount.begin(), colorCount.end());
return answer;
}
DFS도 위의 BFS 풀이와 마찬가지로, 그래프가 12개이니 (같은 색깔이고 상하좌우 연결되어 있는 것들이 하나의 그래프) 이중 for문에서 DFS를 실행한다.
BFS가 더 빠른 것을 확인할 수 있다. 아무래도 DFS는 재귀를 사용해서인 것 같다.
🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄
댓글 남기기