6주차(DFS와 BFS) - [C++]백준2667 단지번호붙이기

10 Apr 2022 in Study on Algorithm

백준2667 단지번호붙이기 링크

문제

예제 입력

---

코드

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

int n, cnt = 0;
int map[25][25];
bool check[25][25];
vector<int> result;

// 방향 이동
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };

void dfs(int x, int y, int cnt){
    if (x <= -1 || x >=n || y <= -1 || y >= n)  return;
    if(map[x][y]==0 || check[x][y] == true) return;

    check[x][y] = true;
    if(map[x][y]==1) map[x][y]=cnt;
    
    dfs(x - 1, y, cnt);
    dfs(x, y - 1, cnt);
    dfs(x + 1, y, cnt);
    dfs(x, y + 1, cnt); 

}

void bfs() {
    queue<pair<int, int> > q;
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (map[i][j] == 1 && check[i][j] == false) {
                int house = 1; // 단지내 가구 수  
                q.push(make_pair(i, j));
                check[i][j] = true;
                cnt++;

                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 (0 <= nx && nx < n && 0 <= ny && ny < n) {
                            if (map[nx][ny] == 1 && check[nx][ny] == false) {
                                q.push(make_pair(nx, ny));
                                check[nx][ny] = true;
                                house++;
                            }
                        }
                    }
                }
                result.push_back(house);
            }
        }
    }
}

int main(void)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); //cin 실행속도 향상
    // 입력
    //cin: 공백 포함
    //문자열을 받을때 애매해지므로 문자열을 받을 경우에는 cin의 멤버함수인 cin.getline()을 사용한다.
    //iostream-cin.ignore(); char c[10]; cin.getline(c, 10, '\n');
    //스트링-getline(cin, str, '\n');
    
    //scanf : 앞 뒤 공백 무시
    //하지만 scanf에서도 만약 scanf("%d", &graph[i][j]); 이를 사용했다면 하나씩 받을 수 없어 오류가 났을 것이다.
    //따라서, 문자를 1개씩 읽어들이기 위해 %1d를 사용해주어야 했다.

    cin >> n;
    string str;
    for (int i = 0; i < n; i++) {
        cin >> str;
        for (int j = 0; j < str.length(); j++) {
            if (str[j] == '1') {
                map[i][j] = 1;
            }
            else map[i][j] = 0;
        }
    }

    //bfs();
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (map[i][j] == 1 && check[i][j] == false) {
                cnt++; // 단지 수 
                dfs(i, j, cnt); 
            }
        }
    }
    for (int k = 1; k <= cnt; k++) {
        int count = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (map[i][j] == k) count++;
            }
        }
        result.push_back(count);
    }
    sort(result.begin(), result.end());
    cout << cnt << "\n";
    for (int i = 0; i < result.size(); i++) {
  		cout << result[i] << "\n";
    }
}

설명

이 문제는 아파트 단지마다 번호가 있듯이 단지수와 뭉쳐있는 건물의 수를 구하는 것입니다. C++ STL(표준 템플릿 라이브러리)에서 Queue를 사용하여 구현했습니다. 건물들을 입력 받아 시작점을 찾으며 같은 단지인 경우 같은 넘버링을 해주며 탐색하는데 BFS 또는 DFS를 변형하여 두 가지 경우로 구현했습니다. BFS는 너비우선 탐색으로 나선형 모습으로 탐색하고 DFS는 깊이우선 탐색으로 특정 방향으로 나가는 모습으로 탐색을 합니다. 그리고 check값을 배정하는데 이것은 같은 곳을 탐색할 수 있는 것을 방지합니다. 그리고 결과값을 오름차순으로 정렬하여 출력했습니다.

-pair<자료형, 자료형> 변수명; : 하나의 변수에 2가지 값을 저장함

<queue>
-queue<자료형> 변수명; : 큐 자료구조 사용

---

결과