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

● [문제번호 2667] 단지번호붙이기

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

2667번: 단지번호붙이기

 

● 알아야 할 것

: vector 자료구조와 메소드

: pair 자료구조와 메소드

: BFS

: DFS (재귀, 비재귀)

 

● 풀이 과정

: BFS, DFS (비재귀)를 구현하면

집이 있는 좌표를 이용해서 구현해야하므로

pair 자료구조를 이용한다.

 

main문

1. 모든 집을 확인하는데

2. 방문한 적 없거나, 지도에 집이 있다면

3. 방문 체크인

4. 함수 진입

↓

BFS, DFS (비재귀) 함수

1. queue, stack에서 원소를 뺄 때마다 단지내 집의 수를 늘린다.

2. 상, 하, 좌, 우를 확인하며 방문하면 되는 경우에

2-1. 방문 체크인

2-2. queue, stack에 저장

3. 반환은 queue, stack이 빌 때 까지 센 단지내 집의 수

 

 

: DFS (재귀)

main문은 위와 동일하고

 

DFS (재귀) 함수

1. 상, 하, 좌, 우를 확인하며 방문하면 되는 경우에

1-1. 방문 체크인

1-2. 재귀

1-3. 재귀의 반환값을 모아야한다.

2. 현재 있는 집까지 포함해서

3. 각 단지내 집의 수 반환

 

● 주의 할 것

: BFS, DFS (비재귀)에서는 if문을 주의해서 작성하면 특별한 어려움 없고

DFS (재귀)를 이용할 때는 현재 있는 집까지 포함해서 반환해야 하는 걸 빠뜨리면 안 된다.

 

● 참고 할 것

: NULL

 

● 풀이 코드

#include <bits/stdc++.h>

using namespace std;

// controlX : 지도를 움직일 때 쓰는 상, 하, 좌, 우
// controlY : 지도를 움직일 때 쓰는 상, 하, 좌, 우
// apt : 각 단지내 집의 수 저장
// aptMap : 초기에 주어지는 지도 입력
// visited : 방문기록
int controlX[4] = {-1, 1, 0, 0};
int controlY[4] = {0, 0, -1, 1};
vector<int> apt;
int aptMap[26][26];
bool visited[26][26];
int N;

// 넓이 우선 탐색
// 기본적인 작성 형태에서 pair 사용, 방문기록 조절
int bfs(int startRow, int startCol)
{
    // 지도의 좌표를 저장하기 위해 pair사용
    queue<pair<int, int>> q;
    
    // bfs 함수 진입 전에 실행했기에 방문 체크인 불필요
    // visited[startRow][startCol] = true;
    q.push(pair<int, int>(startRow, startCol));
    
    // 단지내 집의 수
    int cnt = 0;
    
    while(!q.empty())
    {
        int fromRow = q.front().first;
        int fromCol = q.front().second;
        
        q.pop();
        
        cnt++;
        
        // 상, 하, 좌, 우
        for(int i = 0; i < 4; i++)
        {
            // 방문하면 안되는 4가지
            // 1. 지도의 X축을 벗어난 경우
            if(fromRow + controlX[i] < 0 || N <= fromRow + controlX[i])
                continue;
            // 2. 지도의 Y축을 벗어난 경우
            else if(fromCol + controlY[i] < 0 || N <= fromCol + controlY[i])
                continue;
            // 3. 방문한 적이 있는 경우
            else if(visited[fromRow + controlX[i]][fromCol + controlY[i]])
                continue;
            // 4. 지도에 집이 없는 경우
            else if(aptMap[fromRow + controlX[i]][fromCol + controlY[i]] == 0)
                continue;
            else
            {
                visited[fromRow + controlX[i]][fromCol + controlY[i]] = true;
                q.push(pair<int, int>(fromRow + controlX[i], fromCol + controlY[i]));
            }
        }
    }
    
    // 단지내 집의 수 반환
    // (최소 1개)
    return cnt;
}

// 깊이 우선 탐색 (비재귀)
// 기본적인 작성 형태에서 pair 사용, 방문기록 조절
int dfs(int startRow, int startCol)
{
    // 지도의 좌표를 저장하기 위해 pair사용
    stack<pair<int, int>> s;
    
    // dfs 함수 진입 전에 실행했기에 불필요
    // visited[startRow][startCol] = true;
    s.push(pair<int, int>(startRow, startCol));

    // 단지내 집의 수
    int cnt = 0;
    
    while(!s.empty())
    {
        int fromRow = s.top().first;
        int fromCol = s.top().second;
        
        s.pop();
        
        cnt++;
        
        // 상, 하, 좌, 우
        for(int i = 0; i < 4; i++)
        {
            // 방문하면 안되는 4가지
            // 1. 지도의 X축을 벗어난 경우
            if(fromRow + controlX[i] < 0 || N <= fromRow + controlX[i])
                continue;
            // 2. 지도의 Y축을 벗어난 경우
            else if(fromCol + controlY[i] < 0 || N <= fromCol + controlY[i])
                continue;
            // 3. 방문한 적이 있는 경우
            else if(visited[fromRow + controlX[i]][fromCol + controlY[i]])
                continue;
            // 4. 지도에 집이 없는 경우
            else if(aptMap[fromRow + controlX[i]][fromCol + controlY[i]] == 0)
                continue;
            else
            {
                visited[fromRow + controlX[i]][fromCol + controlY[i]] = true;
                s.push(pair<int, int>(fromRow + controlX[i], fromCol + controlY[i]));
            }
        }
    }
    
    // 단지내 집의 수 반환
    return cnt;
}

// 깊이 우선 탐색 (재귀)
// 기본적인 작성 형태로 구현
int dfs_recursive(int startRow, int startCol)
{
    // 각 단지내 현재집으로부터 남은 집의 수
    // 쉽게말해 각 단지내 집의 수
    int cnt = 0;
    
    // 상, 하, 좌, 우
    for(int i = 0; i < 4; i++)
    {
        // 방문하면 안되는 4가지
        // 1. 지도의 X축을 벗어난 경우
        if(startRow + controlX[i] < 0 || N <= startRow + controlX[i])
            continue;
        // 2. 지도의 Y축을 벗어난 경우
        else if(startCol + controlY[i] < 0 || N <= startCol + controlY[i])
            continue;
        // 3. 방문한 적이 있는 경우
        else if(visited[startRow + controlX[i]][startCol + controlY[i]])
            continue;
        // 4. 지도에 집이 없는 경우
        else if(aptMap[startRow + controlX[i]][startCol + controlY[i]] == 0)
            continue;
        else
        {
            visited[startRow + controlX[i]][startCol + controlY[i]] = true;
            // 앞으로 재귀할 집의 수 모으기
            cnt += dfs_recursive(startRow + controlX[i], startCol + controlY[i]);
        }
    }
    
    // 현재 있는 집까지 포함
    cnt++;
    
    // 각 단지내 집의 수 반환
    return cnt;
}


int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    cin >> N;
    
    // 지도 입력
    for(int r = 0; r < N; r++)
    {
        for(int c = 0; c < N; c++)
        {
            // 한 글자씩 받기 위해 char형 사용
            char input;
            cin >> input;
            
            aptMap[r][c] = input - '0';
        }
    }
    
    // 모든 집을 확인
    for(int r = 0; r < N; r++)
    {
        for(int c = 0; c < N; c++)
        {
            // {방문한 적 없고} + {집이 있는 곳}
            if(!visited[r][c] && aptMap[r][c] != 0)
            {
                visited[r][c] = true;
                // {DFS재귀, DFS비재귀, BFS} 중 1개 선택
                apt.push_back(dfs_recursive(r, c));
                // apt.push_back(dfs(r, c));
                // apt.push_back(bfs(r, c));
            }
        }
    }
    
    // 총 단지수 출력
    cout << apt.size() << "\n";
    
    // 각 단지내 집의 수를 오름차순으로 정렬
    sort(apt.begin(), apt.end());
    
    // 각 단지내 집의 수 출력
    for(auto element : apt)
        cout << element << "\n";
    
    return 0;
}

 

 

● [백준] - [알고리즘 기초 2/2] - [600 - 그래프 1] 문제집

번호	문제 번호	문제 이름	풀이 링크
1	13023	ABCDE	https://pirateturtle.tistory.com/269
2	1260	DFS와 BFS	https://pirateturtle.tistory.com/270
3	11724	연결 요소의 개수	https://pirateturtle.tistory.com/271
4	1707	이분 그래프	https://pirateturtle.tistory.com/272
5	2667	단지번호붙이기	https://pirateturtle.tistory.com/273
6	4963	섬의 개수	https://pirateturtle.tistory.com/274
7	2178	미로 탐색	https://pirateturtle.tistory.com/275
8	7576	토마토	https://pirateturtle.tistory.com/276
9	7562	나이트의 이동	https://pirateturtle.tistory.com/277