[프로그래머스] 카카오프렌즈 컬러링북 (해결과정, BFS, DFS 복기, C++)
| 문제 설명 |
프로그래머스의 카카오프렌즈 컬러링북 문제입니다.
주의사항
- 1 <= m, n <= 100
- picture의 원소는 0 이상 2^31 - 1 이하의 임의의 값이다.
- picture의 원소 중 값이 0인 경우는 색칠하지 않는 영역을 뜻한다.
| 해결 과정 |
BFS
모든 인덱스를 다 순회하지만 똑같은 크기의 배열을 하나 더 둬서 방문한 인덱스를 체크합니다.
기존 배열을 반복 접근한다
값이 0이 아니고 방문한 인덱스가 아니라면 진행
접근한 적 없는 새로운 인덱스(영역) 이기에 전체 영역 수 증가
지금 인덱스와 인접한 같은 값의 인덱스를 전부 접근한다.
같은 값의 인덱스를 큐에 저장하고 채워진 큐가 비워질 때까지 반복해 인접한 동일값 인덱스에 전부 접근한다.
접근하면서 접근한 인덱스의 수를 세어 크기를 가늠한다. 이후 만들어질 다른 영역들과도 비교하여 가장 큰 값을 반환
이후 처음으로 돌아가 값이 0이 아니고 방문한 인덱스가 아닌 경우를 찾아 진행한다.
필요했던 것들
dx[4] = {1,-1,0,0};
dy[4] = {0,0,1,-1};
인접 인덱스 접근위해서 배열
#include <queue>
#include <vector>
#include <algorithm>
#define X first
#define Y second
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
using namespace std;
// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
vector<int> solution(int m, int n, vector<vector<int>> picture) {
int number_of_area = 0;
int max_size_of_one_area = 0;
vector<int> answer(2);
queue<pair<int, int>> q;
int visited[100][100] = {0, };
for (int i=0; i < m; i++)
{
for (int j=0; j < n; j++)
{
if (picture[i][j] != 0 && visited[i][j] == 0)
{
visited[i][j] = 1;
int cur_val = picture[i][j];
number_of_area++;
int one_area_size = 1;
q.push({i,j});
while(!q.empty())
{
pair<int, int> cur = q.front();
for (int dir=0; dir < 4; dir++)
{
int next_x = cur.X+dx[dir];
int next_y = cur.Y+dy[dir];
if (next_x >= m || next_y >= n || next_x < 0 || next_y < 0) continue;
if (picture[next_x][next_y] != cur_val || visited[next_x][next_y] != 0) continue;
visited[next_x][next_y] = 1;
q.push({next_x, next_y});
one_area_size++;
}
q.pop();
}
max_size_of_one_area = max(one_area_size, max_size_of_one_area);
}
}
}
answer[0] = number_of_area;
answer[1] = max_size_of_one_area;
return answer;
}
DFS
BFS와 마찬가지로 한 번 방문한 인덱스를 기억하는 배열을 준비한다.
DFS함수를 통해 얻을 수 있는 각 영역마다의 크기를 저장할 배열을 준비한다.
이후 모든 인덱스에 DFS 함수를 적용시키고 각 영역마다의 크기를 저장한다.
저장한 배열의 사이즈와 가장 큰 요소를 반환한다.
#include <vector>
#include <algorithm>
using namespace std;
int visited[100][100];
vector<vector<int>> pic;
int DFS(int x,int y,int color,int m,int n){
int count=1;
visited[x][y]=1;
if(x!=0 && pic[x-1][y]==color && visited[x-1][y]!=1) count+=DFS(x-1,y,color,m,n);
if(y!=0 && pic[x][y-1]==color && visited[x][y-1]!=1) count+=DFS(x,y-1,color,m,n);
if(x!=m-1 && pic[x+1][y]==color && visited[x+1][y]!=1) count+=DFS(x+1,y,color,m,n);
if(y!=n-1 && pic[x][y+1]==color && visited[x][y+1]!=1) count+=DFS(x,y+1,color,m,n);
return count;
}
// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
vector<int> solution(int m, int n, vector<vector<int>> picture) {
vector<int> answer(2);
pic = move(picture);
vector<int> count_list;
for (int i=0; i < m; i++)
{
for (int j=0; j< n; j++)
{
visited[i][j] = 0;
}
}
for (int i=0; i < m; i++)
{
for (int j=0; j < n; j++)
{
if (pic[i][j] != 0 && visited[i][j] == 0)
{
count_list.push_back(DFS(i, j, pic[i][j], m, n));
}
}
}
answer[0] = count_list.size();
answer[1] = *max_element(count_list.begin(), count_list.end());
return answer;
}
| 느낀 점 (잡설 93% , 배운점 7%(많은 편)) |
BFS, DFS 둘 다 개념만 조금 익혔고 실제로 다루지 못해 잘 몰랐지만
이번 문제를 통해 어느 정도 감이 오는 듯 했다.
해당 문제에서 BFS는 visited라는 중복된 노드의 접근을 방지하며 dx, dy라는 왼쪽, 오른쪽, 위, 아래
의 접근을 큐의 선입선출 특성을 이용해 근처에 있는 노드들부터 접근하며 영역을 넓히는 너비우선탐색의 느낌을
어느 정도 느낄 수 있었다.
DFS는 조건문을 통해 탐색방향의 우선순위를 정해서 접근하는 듯 했다. 전체적인 탐색그림은 문제에 따라
다르겠지만 대략적으로 소용돌이가 연상됐다. 관련문제를 더 풀어보는게 좋을 하다. 그래프 탐색문제 멋지구나 생각이 든다.
int visited[100][100] = {0, }; 선언 시 원소전체를 0으로 초기화
dx, dy 배열로 방향인덱스
등등 많이 배웠습니다~ 호호 *^0^*