[BFS] 백준 2667번 단지 번호 붙이기(C++)

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

 

 

 

[DFS,BFS] 백준 1260번 BFS와 DFS(C++)

 

이문제, 당연히 BFS와 DFS 문제를 풀고 와야 겠지?

 

내용 자체는 쉽다

그림으로만 딱 봐도 보이잖나?

그럼 어떻게 풀까?

 

앞선 BFS나 DFS문제들에선 연결된 NODE들을 통해서 그래프를 그렸는데 이번에도 똑같다

연결된 노드들끼리의 배열이 아닌 연결된 노드들의 갯수만 보면 됨~

 

 

하지만 앞선 문제들은 모두 1차원인데 이건 2차원이다

 

그럼 어떻게 풀까?

 

1. 2차원으로

2. 1차원으로

 

뭔가 반대가된 기분이네

쨋든

 

2차원으로 푸는건 쉽다

bfs 와 dfs로 들어갔을 때 , 그저 queue<pair<int,int>> q 만 새로 해줘서

쌍으로 저장하면 되지만

 

나는 그걸 몰랐다

풀고나서, 인터넷 찾아보니까 저런게 있더라

기본기가 부족한 나는 멍청이

 

난 1차원으로 풀었다

 

배열의 경우 n*n 배열에서

for(i<n)

for(j<n)

이중 중첩문을 통해 들어갔을때,

각각의 배열 원소는 i*n+j잖나

 

뭐 이건 그렇다치고

 

우리가 중요하게 생각해야 할것은

그래프를 떠올리는 것 또한 중요하지만

 

맞닿은 집들끼리 "연결" 해주는 것이 중요하다.

 

코드로 보여주겠다

 

#include <iostream>

#include <vector>

#include <queue>

#include <string>

#include <algorithm>

using namespace std;

bool visited[25 * 25];

vector<int> home[25 * 25];

vector<int> list;

int whole = 0;

int arr[25 * 25];

int n;

void bfs(int alpha);

int main()

{

    cin >> n;

    for (int i = 0; i < n; i++)

    {

        string temp;

        cin >> temp;

        for (int j = 0; j < n; j++)

        {

            arr[i * n + j] = temp[j] - '0';

        }

    }

    for (int i = 0; i < n; i++)

    {

        for (int j = 0; j < n; j++)

        {

            int x = i * n + j;

            if (arr[x])

            {

                if (((x + 1) % n) != 0 && arr[x + 1])

                {

                    home[x].push_back(x + 1);

                    home[x + 1].push_back(x);

                }

                if (!(((x + n) > n * n)) && arr[x + n])

                {

                    home[x].push_back(x + n);

                    home[x + n].push_back(x);

                }

            }

        }

    }

    for (int i = 0; i < n; i++)

    {

        for (int j = 0; j < n; j++)

        {

            int temp = i * n + j;

            if (!visited[temp] && arr[temp] == 1)

                bfs(i * n + j);

        }

    }

    sort(list.begin(), list.end());

    cout << whole << "\n";

    for (int i = 0; i < list.size(); i++)

        cout << list[i] << "\n";

}

void bfs(int alpha)

{

    queue<int> p;

    p.push(alpha);

    int count_ = 1;

    visited[alpha] = true;

    whole++;

    while (!p.empty())

    {

        int temp = p.front();

        p.pop();

        for (int k = 0; k < home[temp].size(); k++)

        {

            if (!visited[home[temp][k]])

            {

                visited[home[temp][k]] = true;

                p.push(home[temp][k]);

                count_++;

            }

        }

    }

    list.push_back(count_);

}

 

 if (arr[x])

            {

                if (((x + 1) % n) != 0 && arr[x + 1])

                {

                    home[x].push_back(x + 1);

                    home[x + 1].push_back(x);

                }

                if (!(((x + n) > n * n)) && arr[x + n])

                {

                    home[x].push_back(x + n);

                    home[x + n].push_back(x);

                }

            }

여기서 보면 알겠지만 arr[x]가 1인 상태에서,

오른쪽 혹은 아래쪽으로 이동하는 것인데

만약 오른쪽으로 옮기고 n으로 나눈 나머지가 0이라면, arr[x]는 맨 오른쪽 끝번이였던 것이고

아래 조건문은 x+n ( 즉 한 칸 바로 아래 )이 전체 크기보다 클때만 고려하면 된다

 

그리고 왜 오른쪽과 아래만하고 , 왼쪽과 위쪽은 안했는가? 라고 생각한다면

 home[x].push_back(x + 1);

home[x + 1].push_back(x);

이렇게 양쪽다 해주고, i와 j가 0부터 증가하니까 이전것은 자동으로 들어가고 고려할 필요가 없다.

 

난 bfs로 풀었는데 dfs로 풀어보쇼