PS/프로그래머스
[프로그래머스/]카카오프렌즈 컬러링북
민팽
2022. 6. 26. 02:29
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 <vector>
#include <queue>
#include <iostream>
using namespace std;
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
int bfs(int i, int j, vector<vector<int>> &v, int m, int n) {
queue<pair<int, int>> q;
q.push({i, j});
int item = v[i][j];
int cnt = 1;
v[i][j] = 0;
while(!q.empty()) {
int x = q.front().first;
int y = q.front().second;
q.pop();
for(int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if(nx < 0 || nx >= m || ny < 0 || ny >= n) continue;
if(v[nx][ny] == item) {
q.push({nx, ny});
v[nx][ny] = 0;
cnt++;
}
}
}
return cnt;
}
// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
vector<int> solution(int m, int n, vector<vector<int>> picture) {
vector<int> answer(2, 0);
for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
if(picture[i][j] != 0) {
answer[0] += 1;
int tmp = bfs(i, j, picture, m, n);
if(tmp > answer[1]) answer[1] = tmp;
}
}
}
return answer;
}
처음에 분명 이거랑 똑같은 코드로 풀었는데 시간초과만 떠서 화가났다.. 어디가 틀린건지 정말 열심히 살펴봤는데 모르겠어서 메모장에 복사해놓고 visited 배열을 추가하여 더 길게 풀어서 제출했다. 그러고 다시 메모장에 있는걸 복붙해서 테스트 코드 실행을 해보니 갑자기 되는거다.. 진짜로 뭐지 내가 무의식중에 코드를 만졌나 싶지만 아무리생각해도 안만졌는데..ㅠㅠ 난 억울하다 ㅠㅠ 프로그래머스는 내 풀이에 최초 정답이었던 코드만 남아서 블로그에 올린다 ㅠ