[프로그래머스][Lv 2] 카카오프렌즈 컬러링북 (2017 카카오코드 예선)

BFS 문제 연습해보고 싶어서 다시 풀어봤다. BFS 연습하기 딱 좋은 문제. 아래 이전 코드와 비교도 해봄(●'◡'●)

 

#include <vector>
#include <queue>
#include <cmath>

using namespace std;

//상하좌우
int dx[4] = { 0,0,-1,1 };
int dy[4] = { 1,-1,0,0 };

bool Visited[100][100];

int bfs(int x, int y, int m, int n, vector<vector<int>>& picture) {
	queue <pair< int, int>> q;
	int area = 1;
	int curX;
	int curY;
	int nextX;
	int nextY;

	q.push(make_pair(x, y));
    
	while (!q.empty()) {
		curX = q.front().first;
		curY = q.front().second;
		q.pop();
        
        //현재 칸의 상하좌우 살펴보기
		for (int i = 0; i < 4; i++) {
			nextX = curX + dx[i];
			nextY = curY + dy[i];
			//같은색이라면 queue에 push
			if (nextX >= 0 && nextY >= 0 && nextX < m && nextY < n && !Visited[nextX][nextY] && picture[nextX][nextY] == picture[curX][curY]) {
				Visited[nextX][nextY] = true;
				q.push(make_pair(nextX, nextY));
				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;

	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			Visited[i][j] = false;
		}
	}

	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			if (picture[i][j] != 0 && !Visited[i][j]) {
				Visited[i][j] = true;
				max_size_of_one_area = max(bfs(i, j, m, n, picture), max_size_of_one_area);
				number_of_area++;
			}
		}
	}

	vector<int> answer(2);
	answer[0] = number_of_area;
	answer[1] = max_size_of_one_area;
	return answer;
}

 

+ 몇년 전에 이 문제 풀었을 때보다 훨씬 깔끔하게 풀었다. 아래는 그때의 코드!ㅋㅋㅋㅋㅋ

방문했던 곳인지 확인하는 걸 ARRAY가 아닌 vector로 만들어서 더 복잡해보이는데 무려 recursion함수를 짜놨다. 이때 아마 엄청 오래걸렸던 것 같은데 노력의 흔적+ 지쳐서 변수명을 엉망진창으로 써놓은게 보인다. 그래도 열심히 했어:D

이때는 변수명을 알아볼 수 없게 짜뒀는데 이제는 그 습관을 고쳤다. 나는 발전 중!!

#include <vector>
#include <algorithm>
#include <iostream>
#include <cstring>

using namespace std;

void recur(int x,int y,int m,int n,vector<vector<int>> picture,vector<vector<int>> &pic);

int countt;

vector<int> solution(int m, int n, vector<vector<int>> picture) {
    vector <vector<int>> pic;
    for(int i = 0; i< m; i++){//갔던길 확인하는 배열
        vector <int> v;
        for(int j = 0; j< n; j++)
            v.push_back(1);
        pic.push_back(v);
    }
    countt = 0;

    int number_of_area = 0;
    int max_size_of_one_area = 0;
    vector <int> area;

    for(int i = 0; i< m; i++){
        for(int j = 0; j< n; j++){
            if((pic[i][j] != -1) && (picture[i][j] !=0)){//가지않은 영역
                recur(i,j,m,n,picture,pic);
                area.push_back(countt);
                countt = 0;
            }
        }
    }
    vector<int> answer(2);
    number_of_area = area.size();
    max_size_of_one_area = *max_element(area.begin(),area.end());
    answer[0] = number_of_area;
    answer[1] = max_size_of_one_area;
    return answer;
}

void recur(int x,int y,int m,int n,vector<vector<int>> picture,vector<vector<int>> &pic){
    int dx[] = {-1, 0, 1, 0};//위 오른 아래 왼
    int dy[] = {0, 1, 0, -1};
    countt++;//영역 크기 ++
    pic[x][y] = -1;//왔던 길 표시

    for(int i = 0;i<4;i++){
        int xx =x + dx[i];
        int yy =y + dy[i];
        if((xx>=m) || (yy>=n) || (xx<0)|| (yy<0)){//그림 벗어남
        }
        else if((picture[x][y] == picture[xx][yy]) &&(pic[xx][yy] != -1) 
            &&(picture[xx][yy] != 0)){//같은 색
            pic[xx][yy] = -1;
            recur(xx,yy,m,n,picture,pic);
        }
    }   
}