📌카카오프렌즈 컬러링북
출판사의 편집자인 어피치는 네오에게 컬러링북에 들어갈 원화를 그려달라고 부탁하여 여러 장의 그림을 받았다. 여러 장의 그림을 난이도 순으로 컬러링북에 넣고 싶었던 어피치는 영역이 많으면 색칠하기가 까다로워 어려워진다는 사실을 발견하고 그림의 난이도를 영역의 수로 정의하였다. (영역이란 상하좌우로 연결된 같은 색상의 공간을 의미한다.)
그림에 몇 개의 영역이 있는지와 가장 큰 영역의 넓이는 얼마인지 계산하는 프로그램을 작성해보자.
위의 그림은 총 12개 영역으로 이루어져 있으며, 가장 넓은 영역은 어피치의 얼굴면으로 넓이는 120이다.
입력 형식
입력은 그림의 크기를 나타내는 m과 n, 그리고 그림을 나타내는 m × n 크기의 2차원 배열 picture로 주어진다. 제한조건은 아래와 같다.
1 <= m, n <= 100
picture의 원소는 0 이상 2^31 - 1 이하의 임의의 값이다.
picture의 원소 중 값이 0인 경우는 색칠하지 않는 영역을 뜻한다
예제 입출력
m = 6, n = 4,
picture = [[1, 1, 1, 0],
[1, 2, 2, 0],
[1, 0, 0, 1],
[0, 0, 0, 1],
[0, 0, 0, 3],
[0, 0, 0, 3]] 일 때
answer = [4, 5]📌풀이
(영역이란 상하좌우로 연결된 같은 색상의 공간을 의미한다.)
그림에 몇 개의 영역이 있는지와 가장 큰 영역의 넓이는 얼마인지 계산하는 프로그램을 작성해보자.
이 문제는 먼저 모든 배열을 돌면서 영역의 개수를 구해야하고, 각 영역 중 가장 큰 사이즈를 return해야 한다.
이 말은 즉 BFS, DFS를 이용하여 최대 값을 구하라는 의미이다!
0. 호출부
//bfs 방식으로 배열을 돌며 영역 개수와 가장 큰 영역의 개수를 구함
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
//아직 방문 전이고, picture[i][j]가 색칠되어 있다면(!0)
if (!visit[i][j] && picture[i][j] > 0)
{
//bfs 사용 시
int area = bfs(i, j, picture);
number_of_area++;
max_size_of_one_area = max_size_of_one_area < area ? area : max_size_of_one_area;
//dfs 사용 시
int area = dfs(i, j, picture);
number_of_area++;
max_size_of_one_area = max_size_of_one_area < area ? area : max_size_of_one_area;
}
}
}1. DFS로 접근 //재귀
int dfs(int x, int y, const vector<vector<int>> pic)
{
int area = 1;
visit[x][y] = true;
for (int i = 0; i < 4; i++) //상하좌우로 검사할꺼라 i는 4 이내
{
//새로 방문 할 nx, ny를 구함
int nx = x + row[i];
int ny = y + col[i];
//nx, ny의 범위 체크
if (nx < 0 || nx >= width || nx < 0 || ny >= height)
continue;
else
{ //범위 내에 들어온다면, 방문여부와 색칠여부에 따라 재귀 호출
if (!visit[nx][ny] && pic[nx][ny] > 0)
{
area += dfs(nx, ny, pic); //재귀로 호출하여 area 값을 더해 최대 영역의 수를 구함
}
}
}
return area;
}2. BFS로 접근 //큐
int bfs(int x, int y, const vector<vector<int>> pic)
{
int color = pic[x][y]; //target
queue<pair<int, int>> q;
q.push({x, y});
visit[x][y] = true;
int area = 1; //영역 내 블록 개수
while (!q.empty())
{
int cur_x = q.front().first;
int cur_y = q.front().second;
q.pop();
//좌 상 하 우로 영역 탐색
for (int i = 0; i < 4; i++)
{
int next_x = cur_x + row[i];
int next_y = cur_y + col[i];
//범위 체크
if ((next_x >= width || next_x < 0 || next_y >= height || next_y < 0))
continue; //함수로 빼니까 segmentation fault 발생.....
else
{ //next_x, next_y가 범위 내에 있다면
//아직 방문하지 않았고, 방문할 pic의 배열이 target과 같다면
if (!visit[next_x][next_y] && pic[next_x][next_y] == color)
{
visit[next_x][next_y] = true;
q.push({next_x, next_y});
area++;
}
}
}
}
return area;
}📌전체 코드
#include <vector>
#include <queue> //bfs
using namespace std;
bool visit[101][101]; // = {false, }; //방문 여부 //**solution 밖에서 초기화 시 정확성 테스트 통과 불가
//좌 상 하 우
int row[4] = {-1, 0, 0, 1};
int col[4] = {0, 1, -1, 0};
int width;
int height;
// bool rangeCheck(int a, int b){
// return (a >= width || a < 0 || b >= height || b < 0) ? false : true;
// }
int dfs(int x, int y, const vector<vector<int>> pic)
{
int area = 1;
visit[x][y] = true;
for (int i = 0; i < 4; i++)
{
int nx = x + row[i];
int ny = y + col[i];
if (nx < 0 || nx >= width || ny < 0 || ny >= height)
continue;
else
{
if (!visit[nx][ny] && pic[nx][ny] > 0)
{
area += dfs(nx, ny, pic); //재귀로 호출하여 area 값을 더해 최대 영역의 수를 구함
}
}
}
return area;
}
int bfs(int x, int y, const vector<vector<int>> pic)
{
int color = pic[x][y]; //target
queue<pair<int, int>> q;
q.push({x, y});
visit[x][y] = true;
int area = 1; //영역 내 블록 개수
while (!q.empty())
{
int cur_x = q.front().first;
int cur_y = q.front().second;
q.pop();
//좌 상 하 우로 영역 탐색
for (int i = 0; i < 4; i++)
{
int next_x = cur_x + row[i];
int next_y = cur_y + col[i];
//범위 체크
if ((next_x >= width || next_x < 0 || next_y >= height || next_y < 0))
continue; //함수로 빼니까 segmentation fault 발생.....
else
{ //next_x, next_y가 범위 내에 있다면
//아직 방문하지 않았고, 방문할 pic의 배열이 target과 같다면
if (!visit[next_x][next_y] && pic[next_x][next_y] == color)
{
visit[next_x][next_y] = true;
q.push({next_x, next_y});
area++;
}
}
}
}
return area;
}
// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
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);
//전역변수 초기화
width = m;
height = n;
for (int i = 0; i <= width; i++)
{
for (int j = 0; j <= height; j++)
{
visit[i][j] = false;
}
}
//bfs 방식으로 배열을 돌며 영역 개수와 가장 큰 영역의 개수를 구하기
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
if (!visit[i][j] && picture[i][j] > 0)
{
//bfs 사용 시
int area = bfs(i, j, picture);
number_of_area++;
max_size_of_one_area = max_size_of_one_area < area ? area : max_size_of_one_area;
//dfs 사용 시
int area = dfs(i, j, picture);
number_of_area++;
max_size_of_one_area = max_size_of_one_area < area ? area : max_size_of_one_area;
}
}
}
answer[0] = number_of_area;
answer[1] = max_size_of_one_area;
return answer;
}회고
1. segmentation fault 발생
// dfs, bfs 탐색할 때 새 x,y의 값 범위 체크 시 사용하는 함수
bool rangeCheck(int a, int b){
return (a >= width || a < 0 || b >= height || b < 0) ? false : true;
}
//호출 부(dfs, bfs 내)
if (rangeCheck(next_x, next_y))
continue;- 이렇게 작성하면 이상하게 세그멘테이션 폴트가 발생한다.... return의 조건 값을 그대로 가져와 붙이면 돌아간다. 이유가 뭘까.....? 혹시 아는 사람이 있다면 알려주시면 감사하겠다......
2. 시키는 대로 잘 좀 하자
솔루션 함수 위에는 다음과 같이 주석이 달려있다.
// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
vector<int> solution(int m, int n, vector<vector<int>> picture)- 처음 visit 배열을 전역변수에서 초기화를 해두었더니 채점 시 실패가 발생했다.
- 질문하기에 들어가서 질문들을 읽어보니 솔루션 내에서 해주면 된다는 글을 보고 해보니 정말 됐다.
- ㅎㅎ.. 말 좀 잘 듣자..
참고자료
'코딩테스트 공부 > Programmers' 카테고리의 다른 글
| [C++] level2 2개 이하로 다른 비트 77885 (0) | 2021.08.21 |
|---|---|
| [C++] level2 게임 맵 최단거리 1844 (0) | 2021.08.21 |
| [C++] level2 예상대진표 12985 (0) | 2021.08.21 |
| [C++] level2 오픈채팅방 42888 (0) | 2021.08.21 |
| [C++] level2 멀쩡한 사각형 62048 (0) | 2021.08.21 |
댓글