728x90
level 2 : 카카오 프렌즈 컬러링북
https://programmers.co.kr/learn/courses/30/lessons/1829
코딩테스트 연습 - 카카오프렌즈 컬러링북
6 4 [[1, 1, 1, 0], [1, 2, 2, 0], [1, 0, 0, 1], [0, 0, 0, 1], [0, 0, 0, 3], [0, 0, 0, 3]] [4, 5]
programmers.co.kr
코드
//프로그래머스 카카오 프렌즈 컬러링북
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
bool visited[101][101];
int ni[4], nj[4];
int m_copy;
int n_copy;
int size_of_one_area;
void DFS(int cur_i, int cur_j, vector<vector<int>>& picture) {
visited[cur_i][cur_j] = true;
size_of_one_area++;
for (int i = 0; i < 4; i++) {
int next_i = cur_i + ni[i];
int next_j = cur_j + nj[i];
if (next_i < 0 || next_i >= m_copy || next_j < 0 || next_j >= n_copy)
continue;
if (visited[next_i][next_j] == false && picture[next_i][next_j] == picture[cur_i][cur_j]) {
DFS(next_i, next_j, picture);
}
}
}
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);
//전역변수 초기화
memset(visited, 0, sizeof(visited));
ni[0] = 1; ni[1] = 0; ni[2] = -1; ni[3] = 0;
nj[0] = 0; nj[1] = 1; nj[2] = 0; nj[3] = -1;
m_copy = m;
n_copy = n;
size_of_one_area = 0;
for (int i = 0; i < m; i++) { //세로
for (int j = 0; j < n; j++) { //가로
if (picture[i][j] != 0 && visited[i][j] == false) {
size_of_one_area = 0;
DFS(i, j, picture);
number_of_area++;
max_size_of_one_area = max(max_size_of_one_area, size_of_one_area);
}
}
}
answer[0] = number_of_area;
answer[1] = max_size_of_one_area;
return answer;
}
int main() {
int m = 6;
int n = 4;
vector<vector<int>> 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} };
solution(m, n, picture);
return 0;
}
설명
- 이번 문제는 DFS(깊이 우선 탐색)를 이용하여 문제를 해결했다.
- 모든 배열을 방문하여 0이 아니고 방문하지 않았던 위치부터 DFS를 시작한다.
- 같은 영역을 모두 방문한다. ni, nj로 상하좌우 모두 확인한다.
- 몇 개의 영역과 가장 큰 영역을 구한다.
고찰
걸린시간 : 40분
DFS문제나 BFS문제는 여러번 풀어봐서 어떻게 풀어야하는지 감이 온다.
이번 문제는 전역변수를 함수 내에 초기화를 해주어야하는 코드가 있어야 한다. 이게 어떤 것을 의미히는지 잘 몰랐지만 말 그대로 초기화를 또 해주어야 했다. 질문하기에서 초기화를 해주어야하는 말이 있어서 초기화를 해주었더니 테스트 케이스를 성공할 수 있었다.
728x90
'알고리즘 > 프로그래머스' 카테고리의 다른 글
알고리즘(C++) / 프로그래머스 위클리 챌린지 : 5주차 모음 (0) | 2021.08.31 |
---|---|
알고리즘(C++) / 프로그래머스 위클리 챌린지 : 4주차 직업군 추천하기 (0) | 2021.08.31 |
알고리즘(C++) / 프로그래머스 level 2 : 수식 최대화 (0) | 2021.08.29 |
알고리즘(C++) / 프로그래머스 level 2 : 순위 검색 (0) | 2021.08.29 |
알고리즘(C++) / 프로그래머스 level 2 : 튜플 (0) | 2021.08.27 |
댓글