[BOJ알고리즘, C++]#2667_단지 번호 붙이기, 그래프 탐색, BFS, scanf 활용

 

#1. 문제

2667번: 단지번호붙이기

 

---

 

#2. 풀이

 

1. 그래프 탐색

[자료구조]#6_그래프

 

그래프의 모든 정점을 탐색하는 방법은 두 가지입니다. 먼저, DFS(깊이 우선 탐색)은 출발 정점으로부터 더 이상 확장할 수 없는 단말 노드까지 먼저 탐색하는 방법입니다. DFS는 일반적으로 재귀 호출 혹은 스택을 활용하여 구현합니다. 다음으로, BFS(너비 우선 탐색)은 현재 정점과 인접한 정점들을 우선 탐색하는 방법입니다. BFS는 일반적으로 큐를 활용하여 구현합니다.

 

2. 입력 코드 작성 주의! 미로 찾기 종류의 문제는 BFS 활용!

 

1. 먼저, 공백 없이 주어지는 숫자 목록은 scanf("%1d", &tmp)로 입력받아야 합니다.
2. BFS를 수행하여 주어진 2차원 배열 형식의 지도를 탐색하며 각 단지 수를 찾아서 저장합니다.
3. sort 함수를 활용해 오름차순 정렬하고, 정답을 출력합니다.

 

---

 

#3. 코드

 

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

typedef pair<int, int> p;

int N;
vector<vector<int>> map;
vector<vector<bool>> visited;
vector<int> complex;

int dy[] = {0, 0, -1, 1};
int dx[] = {1, -1, 0, 0};

void bfs(p house)
{
    queue<p> q;
    int cnt = 1;

    q.push(house);
    visited[house.first][house.second] = true;

    while (!q.empty())
    {
        int cy = q.front().first;
        int cx = q.front().second;
        q.pop();

        for (int i = 0; i < 4; ++i)
        {
            int ny = cy + dy[i];
            int nx = cx + dx[i];

            if (ny >= N || ny < 0 || nx >= N || nx < 0 || map[ny][nx] == 0 || visited[ny][nx])
                continue;
            q.push({ny, nx});
            visited[ny][nx] = true;
            cnt++;
        }
    }

    complex.push_back(cnt);
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> N;

    map.resize(N, vector<int>(N));
    visited.resize(N, vector<bool>(N, false));

    // 입력 관련 주의 사항 : 공백없이 주어지는 정수 입력은 "%1d"를 활용하는 scanf를 활용합니다.
    for (int i = 0; i < N; ++i)
        for (int j = 0; j < N; ++j)
            scanf("%1d", &map[i][j]);

    for (int i = 0; i < N; ++i)
        for (int j = 0; j < N; ++j)
            if (!visited[i][j] && map[i][j] == 1)
                bfs({i, j});

    sort(begin(complex), end(complex));

    cout << complex.size() << '\n';
    for (int i = 0; i < (int)complex.size(); ++i)
        cout << complex[i] << '\n';

    return 0;
}

 

---