백준 2667번 단지번호붙이기

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

DFS(Depth First Search) 혹은 BFS(Breadth First Search) 모두 사용할 수 있는 문제였지만 저는 DFS를 이용해 문제를 해결했습니다.

대각선은 고려하지 않으므로 Dir형 배열을 통해 상하좌우를 확인하여 각 단지 내 집을 파악하였고 한 단지 내 DFS를 끝내면 집의 수를 residance 벡터에 추가했습니다.

총 단지 수는 residance 벡터의 size를 출력해주면 되고 residance를 정렬하여 모두 출력해주면 간단히 AC 받을 수 있는 문제였습니다!

#include <iostream>

#include <string>

#include <vector>

#include <algorithm>

using namespace std;

 

const int MAX = 25;

 

typedef struct

{

        int y, x;

}Dir;

 

Dir moveDir[4] = { {1, 0}, {-1, 0}, {0, 1}, {0, -1} };

 

int N;

int cnt; //각 단지 내 집 수

string graph[MAX];

vector<int> residance; //단지 내 집 수 저장용 벡터

bool visited[MAX][MAX];

 

 

void DFS(int y, int x)

{

        cnt++; //단지 내 집의 수를 센다

        visited[y][x] = true;

 

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

        {

                 int nextY = y + moveDir[i].y;

                 int nextX = x + moveDir[i].x;

 

                 if (0 <= nextX && nextX < N && 0 <= nextY && nextY < N) //범위 내에 있고

                         if (graph[nextY][nextX] == '1' && visited[nextY][nextX]==false) //아직 방문하지 않은 집

                                 DFS(nextY, nextX);

        }

}

 

int main(void)

{

        cin >> N;

 

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

                 cin >> graph[i];

 

 

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

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

                 {

                         if (graph[i][j] == '1' && visited[i][j] == false)

                         {

                                 cnt = 0;

                                 DFS(i, j);

                                 residance.push_back(cnt);

                         }

                 }

 

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

 

        cout << residance.size() << endl;

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

                 cout << residance[i] << endl;

 

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~