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

문제

 

 

시행 착오

없음

 

 

해결 방법

순회하며 1을 찾고, 1을 찾은 위치에서 DFS 를 이용해 상하, 좌우에 1이 없을 때까지 탐색했다.

 

아래는 문제풀이 전에 직접  VS 에 작성한 방법이다.

DP 를 풀듯 차근차근 생각하는 것이 도움이 많이 되는 것 같다.

생각해 본 해결방법
  
1. 상하, 좌우 이렇게 두 경우만 집이 붙어있는 경우이다.
2. DFS / BFS 중 어느거라도 사용한다.
3. 몇 개가 붙어있는지 세고 오름차순으로 출력한다.

 

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>


using namespace std;
vector<int> v;
int N;
int map[26][26];
bool visited[26][26] = { false };
int cnt = 0;

void DFS(int curY, int curX)
{
    if ( curY < 0 || curX < 0 || curY >= N || curX >= N || visited[curY][curX] ) return;

    cnt += 1;

    visited[curY][curX] = true;


        if (!visited[curY+1][curX] && map[curY+1][curX] == 1)
        {
            DFS(curY + 1, curX);
            
        }
        if (!visited[curY][curX+1] && map[curY][curX+1] == 1)
        {
            DFS(curY, curX + 1);
            
        }
        if (!visited[curY][curX-1] && map[curY][curX-1] == 1)
        {
            DFS(curY , curX - 1);
            
        }
        if (!visited[curY-1][curX] && map[curY-1][curX] == 1)
        {
            DFS(curY - 1, curX);
           
        }
    
    

}
int main() {    

    /*
    * 생각해 본 해결방법
    * 
    * 1. 상하, 좌우 이렇게 두 경우만 집이 붙어있는 경우이다.
    * 2. DFS / BFS 중 어느거라도 사용한다.
    * 3. 몇 개가 붙어있는지 세고 오름차순으로 출력한다.
    */
   
    cin >> N;


    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++)
        {
            cnt = 0;
            if (!visited[i][j] && map[i][j] == 1)
            {
                
                DFS(i, j);
                v.push_back(cnt);

            }
        }
    }

    sort(v.begin(), v.end());
    cout << v.size() << '\n';
    for (auto i : v)
    {
        cout << i << '\n';
    }

    return 0;
}