[백준] 2667 단지번호붙이기 c++

 

문제링크 https://www.acmicpc.net/problem/2667

DFS와 BFS 둘다 이용해서 풀이했다.

DFS 주의사항

• dfs재귀 함수를 호출할 때마다 count를 증가해선 안된다.--> dfs(nx,ny,count+1)이런식으로 매개변수로 넣으면 안된다는 뜻. 
• 그 이유는, 일직선 상으로 생기지 않고 (ㅓ,ㅗ,ㅏ,ㅗ) <-이런 모양으로 생긴 동네의 경우 실제 집의 갯수보다 적게 호출되는 경우가 발생하기 때문.
• 따라서 dfs로 탐색하다가 범위 내의 방문하지 않은 곳을 찾으면 곧바로 +1을 해주면 된다.

 

>DFS풀이

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;
const int MAX = 26;
int n;
string arr[MAX];
bool visited[MAX][MAX];
int sum;
vector<int> answer; //정답 배열
int dir[4][2] = { {-1,0},{1,0},{0,1},{0,-1} };
int dist; //인접한 집의 갯수
 
void dfs(int x, int y) {
    for (int i = 0; i < 4; i++) {
        int nx = x + dir[i][0];
        int ny = y + dir[i][1];
        if (visited[nx][ny])
            continue;
        if (nx < 0 || nx >= n || ny < 0 || ny >= n)
            continue;
        if (arr[nx][ny] == '0')
            continue;
        visited[nx][ny] = true;
        dist++;
        dfs(nx, ny);
    }
}
 
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]) {
                dist = 1; //첫 동네 +1
                visited[i][j] = true;
                dfs(i, j);
                answer.push_back(dist);
            }
        }
    }
 
    sort(answer.begin(), answer.end());
    cout << answer.size() << endl;
    for (auto i : answer)
        cout << i << endl;
 
}
 

>BFS풀이

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;
const int MAX = 26;
int n;
string arr[MAX];
bool visited[MAX][MAX];
vector<int> answer; //정답 배열
int dir[4][2] = { {-1,0},{1,0},{0,1},{0,-1} };
int dist; //인접한 집의 갯수
 
void bfs(int x, int y) {
    dist++; //첫 동네 +1을 해줌
    queue<pair<int, int>> q;
    q.push({ x,y });
    while (!q.empty()) {
        int frontx = q.front().first;
        int fronty = q.front().second;
        q.pop();
        for (int i = 0; i < 4; i++) {
            int nx = frontx + dir[i][0];
            int ny = fronty + dir[i][1];
            if (visited[nx][ny])
                continue;
            if (nx < 0 || nx >= n || ny < 0 || ny >= n)
                continue;
            if (arr[nx][ny] == '0')
                continue;
 
            visited[nx][ny] = true;
            q.push({ nx,ny });
            dist++;
        }
    }
}
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]) {
                visited[i][j] = true;
                dist = 0;
                bfs(i, j);
                answer.push_back(dist); 
            }
        }
    }
    sort(answer.begin(), answer.end());
    cout << answer.size() << endl;
    for (auto i : answer)
        cout << i << endl;
 
}