-
[Programmers][C++] 카카오프렌즈 컬러링북Algorithm/Programmers 2022. 3. 8. 17:26
문제 유형 : BFS
https://programmers.co.kr/learn/courses/30/lessons/1829
나의 풀이
카카오 기출문제로 일반적인 BFS문제입니다. 각각의 구분 칸의 갯수와 최대 넓이를 구하는 것으로 동서남북 dir 2차원 배열을 선언해주고, picture의 크기만큼 BFS를 돌리는데 문제 조건에 따라 이미 방문처리가 되어있거나, 0이면 실행하지 않습니다. BFS함수가 실행이 된다는건 영역의 갯수가 1증가된다는 말과 동치입니다. 따라서 실행 될 때마다 영역의 갯수를 증가시켜줍니다. 그 후 선언된 queue에 pos 구조체가 들어갈 때마다 넓이를 1씩 증가시켜주고, 기존의 크기와 비교하여 갱신시켜줍니다. picture의 크기를 다 돌면 answer vector에 [영역의 갯수, 최대 영역의 넓이]를 넣어주면 끝입니다. : )
* C++ Code
#include <vector> #include <queue> #include <algorithm> using namespace std; struct pos{ int y, x; }; bool visited[100][100]; int dir[4][2] = { {-1, 0}, {0, 1}, {1, 0}, {0, -1} }; int number_of_area; int max_size_of_one_area; bool inBound(int y, int x, int m, int n) { return y >= 0 && y < m && x >= 0 && x < n; } void bfs(int m, int n, int l, int k, vector<vector<int>>& picture){ int area = 1; queue<pos> q; q.push({l, k}); ++number_of_area; while (!q.empty()) { int y = q.front().y; int x = q.front().x; visited[y][x] = true; q.pop(); for (int i = 0; i < 4; i++) { int my = y + dir[i][0]; int mx = x + dir[i][1]; if (!inBound(my, mx, m, n)) continue; if (!visited[my][mx] && (picture[y][x] == picture[my][mx])) { visited[my][mx] = true; q.push({my, mx}); ++area; } } } max_size_of_one_area = max(max_size_of_one_area, area); } vector<int> solution(int m, int n, vector<vector<int>> picture) { number_of_area = 0; max_size_of_one_area = 0; for (int i = 0; i < 100; i++) { for (int j = 0; j < 100; j++) { visited[i][j] = false; } } for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (!visited[i][j] && picture[i][j] != 0) bfs(m, n, i, j, picture); } } vector<int> answer(2); answer[0] = number_of_area; answer[1] = max_size_of_one_area; return answer; }
'Algorithm > Programmers' 카테고리의 다른 글
[Programmers][C++][Java] 크레인 인형뽑기 게임 (0) 2022.03.05 [Programmers][C++] 신규 아이디 추천 (0) 2022.03.05 [Programmers][C++] 로또의 최고 순위와 최저 순위 (0) 2022.03.05