Beakjoon 2667 단지번호붙이기

10 Jan 2021 in Algorithm

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

나의 풀이

이 문제는 DFS, BFS로 지난번에 풀었던 1112 유기농 배추 문제와 매우 유사한 방식으로 문제를 해결할 수 있다. 유기농 배추 문제는 DFS로 단순하게 몇개의 구역으로 이루어져 있는지 확인만 하면 되었지만 이 문제의 경우 구역(단지)의 개수 뿐 아니라 각 단지내 집의 수를 구해야한다. 단지내 집의 수를 구하기 위해서는 DFS를 수행할 때 마다 몇개의 노드를 방문했는지만 반환해주면 된다.

풀이 코드 : 2667 단지번호붙이기

#include <stdio.h>
#include <vector>
#include <string.h>
#include <string>
#include <algorithm>
#include <iostream>

using namespace std;

string map[25];
int visit[25][25];

int dfs(int start_x, int start_y){
    vector<pair<int,int>> stack;
    stack.push_back(make_pair(start_x, start_y));
    int count = 0;
    while(!stack.empty()){
        pair<int, int> xy = stack.back();
        int x = xy.first;
        int y = xy.second;
        stack.pop_back();
        if(visit[y][x] == 0){
            count++;
            visit[y][x] = -1;
            if( x-1 >= 0 && visit[y][x-1] == 0 && map[y][x-1] == '1' )
            {
                stack.push_back(make_pair(x-1, y));
            }
            if( x+1 < 25 && visit[y][x+1] == 0 && map[y][x+1] == '1'){
                stack.push_back(make_pair(x+1, y));
            }
            if( y-1 >= 0 && visit[y-1][x] == 0 && map[y-1][x] == '1'){
                stack.push_back(make_pair(x, y-1));
            }
            if( y+1 < 25 && visit[y+1][x] == 0 && map[y+1][x] == '1'){
                stack.push_back(make_pair(x, y+1));
            }
        }
    }
    return count;
}

int main(){
    int N;
    scanf("%d",&N);
    vector<pair<int, int>> node;
    for(int i = 0;i<N;i++){
        cin>>map[i];
        for(int j=0;j<N;j++){
            if(map[i][j] == '0') 
                visit[i][j] = -1;
            else 
                node.push_back(make_pair(j ,i));
        }

    }

    vector<int> answer;
    for(int i=0;i<node.size();i++){
        int x = node[i].first;
        int y = node[i].second;
        if(visit[y][x] == 0){
            answer.push_back(dfs(x,y));
        }
    }

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

    printf("%d\n",answer.size());
    for(int i = 0;i<answer.size();i++){
        printf("%d\n", answer[i]);
    }

}

채점결과