[ 백준 2667 ] 단지번호붙이기 (C++)

https://www.acmicpc.net/problem/2667

2667번: 단지번호붙이기

 

경로 탐색 문제로, bfs와 dfs로 어렵지 않게 풀 수 있다. 두 가지 방법으로 모두 풀어 보았다. 그냥 단순히 모든 경로를 검사하면서 1이 적힌 위치에 가면 그 위치부터 bfs 또는 dfs를 돌리면 된다. 이때 count라는 변수를 두어 단지 안에 번호가 몇 개 있는지 세어준다. 모든 번호를 answer라는 벡터에 저장한 후, 마지막에 벡터를 정렬하고 출력해주기만 하면 된다.

 

 

bfs 풀이

 

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

int N, map[25][25], visit[25][25];
char c;
vector<int> answer;

int bfs(int row, int col){
    vector<pair<int, int>> move = {{1,0}, {-1,0}, {0,1}, {0,-1}};
    int cnt = 0, x, y, m_x, m_y;

    queue<pair<int, int>> q;
    q.push({row, col});
    visit[row][col] = 1;
    cnt++;
    
    while(!q.empty()){
        x = q.front().first;
        y = q.front().second;
        q.pop();
                
        for(int i = 0; i < 4; i++){
            m_x = x + move[i].first;
            m_y = y + move[i].second;
            if(m_x >= 0 && m_x < N && m_y >= 0 && m_y < N){
                // 범위 초과 안 하면 - 1이고 방문 안했으면 push
                if(map[m_x][m_y] == 1 && !visit[m_x][m_y]){
                    q.push({m_x, m_y});
                    visit[m_x][m_y] = 1;
                    cnt++;
                }
            }
        }
    }
    
    return cnt;
}

int main(){
    char c;
    cin >> N;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> c;
            map[i][j] = c - '0';
        }
    }
    
    
    //하나씩 확인, 1이면 bfs()으로 값 반환받고 answer에 push
    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            if(map[i][j] == 1 && !visit[i][j])
                answer.push_back(bfs(i, j));
        }
    }
    
    sort(answer.begin(), answer.end());
    cout << answer.size() << endl;
    for(int elem : answer)
        cout << elem << endl;
    
    return 0;
}

 

dfs 풀이

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int N, map[26][26], visit[26][26];
vector<int> houses; // 단지마다 아파트 수 저장 벡터
int m_row[] = { 1, -1, 0, 0 };
int m_col[] = { 0, 0, 1, -1 };
char c;

void dfs(int row, int col, int& count) {
	if (visit[row][col]) // 방문했으면 리턴
		return;

	visit[row][col] = 1; // 방문처리
	count++; // 아파트수 + 1
	for (int i = 0; i < 4; i++) {
		int xx = row + m_row[i];
		int yy = col + m_col[i];
		if (xx >= 1 && xx <= N && yy >= 1 && yy <= N) { // 범위 검사
			if (!visit[xx][yy] && map[xx][yy]) // 방문하지 않았고 아파트 존재하면 탐색
				dfs(xx, yy, count);
		}
	}
}

int main() {
	cin >> N;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			cin >> c;
			map[i][j] = c - '0';
		}
	}

	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			if (map[i][j] && !visit[i][j]) { // 방문하지 않았고 아파트 존재하면 새로운 단지
				int count = 0;
				dfs(i, j, count);
				houses.push_back(count);
			}
		}
	}

	sort(houses.begin(), houses.end());
	cout << houses.size() << endl;
	for (int elem : houses)
		cout << elem << endl;

	return 0;
}