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

 

 

문제

소스코드

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
constexpr int MAX_N = 26;
 
 
using Point = std::pair<int, int>;
 
struct Node {
    int value_;
    bool visited_;
};
 
 
void BFS(std::vector <std::vector<Node>>& graph, int N) {
    std::queue<Point> queue;
    std::vector<int> result;
    int count{};
    int total{};
 
    for (int xpos = 0; xpos < N; ++xpos) {
        for (int ypos = 0; ypos < N; ++ypos) {
            if (graph[xpos][ypos].visited_ == true)continue;
 
            queue.emplace(Point{ xpos,ypos });
            count = 0;
            while (queue.empty() == false) {
                auto frontValue = queue.front();
 
                queue.pop();
                int x = frontValue.first;
                int y = frontValue.second;
                graph[x][y].visited_ = true;
 
                if (graph[x][y].value_ == 0)
                    break;
 
                //상
                if (y >= 1) {
                    if (graph[x][y - 1].value_ == 1 && graph[x][y - 1].visited_ == false) {
                        graph[x][y - 1].visited_ = true;
                        queue.emplace(Point{ x, y - 1 });
                    }
                }
                //하
                if (y <= N) {
                    if (graph[x][y + 1].value_ == 1 && graph[x][y + 1].visited_ == false) {
                        graph[x][y + 1].visited_ = true;
                        queue.emplace(Point{ x, y + 1 });
                    }
                }
                //좌
                if (x >= 1) {
                    if (graph[x - 1][y].value_ == 1 && graph[x - 1][y].visited_ == false) {
                        graph[x - 1][y].visited_ = true;
                        queue.emplace(Point{ x - 1, y });
                    }
                }
                //우
                if (x <= N) {
                    if (graph[x + 1][y].value_ == 1 && graph[x + 1][y].visited_ == false) {
                        graph[x + 1][y].visited_ = true;
                        queue.emplace(Point{ x + 1, y });
                    }
                }
                ++count;
            }
            if (count != 0) {
                result.emplace_back(count);
                ++total;
            }
        }
    }
 
    std::cout << total << "\n";
    std::sort(result.begin(), result.end(), std::less<int>());
 
    for (const auto& i : result)
        std::cout << i << "\n";
 
}
 
int main() {
    int N;
    std::cin >> N;
    std::vector<std::vector<Node>>v(N+1,std::vector<Node>(N+1));
 
    for (int x = 0; x < N; ++x) {
        for (int y = 0; y < N; ++y) {
            int value;
            scanf("%1d", &value);
            v[x][y] = Node{ value,false };
        }
    }
    BFS(v,N);
}

 

 

후기

 

이 문제를 해결하기 위한 키워드는 BFS이다.

 

BFS(Breadth First Search)는 탐색방법 중 하나로 시작 정점부터 인접 정점을 모든 방문하는 탐색 알고리즘이다.

BFS에는 인접 리스트 방식과 인접 행렬 두 가지 방식으로 탐색이 가능한대 여기서는 인접 행렬 방식으로 문제를 풀었다.

 

scanf("%1d", &value)를 통해 입력받는 숫자를 1개로 줄여서 각 행렬마다 1 또는 0의 값을 가지게 했으며

배열의 크기가 크지 않아서 모든 배열에 대한 상, 하, 좌, 우 방향을 탐색해서 단지를 탐색했다. 인접 행렬에서의 BFS의

시간 복잡도는 O(V^2)이다. 더 자세한 BFS에 관한 내용은 아래 관련 글에 있다.

 

 

인접 행렬을 이용한 BFS 은 처음이었는데 다른 사람들이 푼 방법을 보니 상, 화, 좌, 우를 볼 필요가 없어서 불필요한 연산을 한 거 같다.  Color Scripter에 티스토리 복사가 안돼서 다시 티스토리에 내장되어있는 코드 블록으로 변경하였다. 이번에는

Syntax Highlight 플러그인을 추가했는데 괜찮은거 같다.

 

출처 및 레퍼런스

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

 

관련 글

[자료구조 알고리즘/그래프(Graph)와 트리(Tree)] - 그래프(Graph)

[자료구조 알고리즘/탐색 알고리즘(Search)] - 너비 우선 탐색(Breadth First Search)

[온라인 코딩/탐색(Search)] - [백준] 1260번 DFS와 BFS

[온라인 코딩/탐색(Search)] - [백준] 2606번 바이러스