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

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

2667번: 단지번호붙이기

 

---

⊙ 문제

⊙ 입력

⊙ 출력

⊙ 예제 입출력

⊙ 알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색
• 깊이 우선 탐색

 

---

 

⊙ 문제 접근 과정

 

BFS나 DFS 둘 중 아무거나 사용해도 상관없다. 이번 문제에서 퉁이리는 BFS를 이용해 풀었다.

BFS로 count 값을 올려주었다. 단지가 끝나면 count 값을 result vector에 넣어준다.

그리고 이중 for문이 모두 끝나면 result vector 안에는 단지 수가 들어있다.

 

sort() 함수를 통해 오름차순 정렬을 한 후 size()함수로 개수를 출력하고

차례대로 for문을 통해 result 원소 값을 출력한다.

---

 

⊙ 문제 풀이

 

#include <iostream>
#include <queue>
#include <algorithm>

using namespace std;
#define MAX 26

int n,cnt=0;
string arr[MAX];
bool visited[MAX][MAX]={0,};
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
vector<int> result;
queue<pair<int,int>> q;

void bfs(int x,int y) {
    q.push({x,y});
    visited[x][y]=true;
    cnt++;

    while(!q.empty()) {
        int a = q.front().first;
        int b = q.front().second;
        q.pop();
        for(int i=0;i<4;i++) {
            int nx = a + dx[i];
            int ny = b + dy[i];
            if(0<=nx && 0<=ny && nx <n && ny < n && visited[nx][ny]==false && arr[nx][ny]=='1') {
                q.push({nx,ny});
                visited[nx][ny]=true;
                cnt++;
            }
        }
    }
}

int main() {
    cin >> n;

    for(int i=0;i<n;i++)
        cin >>arr[i];
    
    for (int i=0;i<n;i++) {
        for(int j=0;j<n;j++) {
            if(arr[i][j]=='1' && visited[i][j]==false) {
                cnt =0;
                bfs(i,j);
                result.push_back(cnt);
            }
        }
    }

    sort(result.begin(),result.end());
    
    cout << result.size() << "\n";
    for (int i=0;i<result.size();i++) {
        cout << result[i] << "\n";
    }
}

---

⊙ 결과

 

---

⊙ 마무리

 

 

DFS, BFS 문제를 여러번 반복하여 연습하자

 

좋아요는 로그인하지 않아도 누를 수 있습니다!