99클럽 코테 스터디 14일차 TIL : 단지번호붙이기

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

 

 

저번에 코드트리 조별과제를 하면서

DFS 연습문제에 있던것과 거의 유사했다!

https://usowelcome.tistory.com/55

7/25 TIL : DFS

(마을 구분하기 문제)

 

그래서 간단하게 풀었는데...

 

이번에 할때는 BFS로 해결했고

예전에 풀었을때는 DFS로 풀었다!.. 이런차이점이!!!!

 

근데,,,,,, 어짜피 특정 마을구간안에 모든 칸을 방문해봐야 하므로, DFS든 BFS든 상관없을것같긴한데,,, 차이가 있으려나?

질문게시판을 살펴봐도 DFS BFS 다양하게 푸는것같았다.

 

---

오늘의 문제 - 단지번호 붙이기

=> BFS로 풀이 == 큐를 이용함!

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <string>
using namespace std;

int n;
vector<vector<int>> maps;
vector<int> dx = {1, 0, -1, 0};
vector<int> dy = {0, 1, 0, -1};

vector<int> get_seed(){
    for(int i = 0; i<n; i++){
        for(int j = 0; j<n; j++){
            if(maps[i][j] == 1){
                return {i, j};
            }
        }
    }
    return {-1, -1};
}


int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n;
    maps = vector<vector<int>>(n, vector<int>(n, 0));
    for(int i = 0; i<n; i++){
        string str;
        cin >> str;
        for(int j = 0; j<n; j++){
            maps[i][j] = str[j] - '0';
        }
    }
    

    vector<int> vuliges;
    while(true){
        vector<int> seed = get_seed();
        if(seed[0] == -1){
            break;
        }
        int vuls = 1;
        queue<vector<int>> que;
        que.push(seed);
        maps[seed[0]][seed[1]] = 0;
        while(!que.empty()){
            vector<int> nowindex = que.front();
            que.pop();
            for(int i = 0; i<4; i++){
                int newx = nowindex[0] + dx[i];
                int newy = nowindex[1] + dy[i];
                if(newx < 0 || newx >= n|| newy < 0 || newy >= n){
                    continue;
                }
                if(maps[newx][newy] == 1){
                    vuls++;
                    maps[newx][newy] = 0;
                    que.push({newx, newy});
                }
            }
        }
        vuliges.push_back(vuls);

    }

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

    cout << vuliges.size()<<endl;
    for(int i = 0; i<vuliges.size(); i++){
        cout << vuliges[i] << endl;
    }


    return 0;
}

백준문제에서 좀 애먹은 부분은 입력부분이었다.

지금까지 저렇게 map이 주어질때는

1. 띄어쓰기로 구분되어있거나

2. 문자여서 char로 받아올 수 있거나

두가지 경우였다.

근데 이번에는 띄어쓰기도 없고,, 문자로 받아오긴 싫고,,

그래서 한줄받고, 거기서 01010101로 바꿔주는 식으로 처리해주었다!!

사실 그냥 char로 받아오는게 일관성있겠지만,, 난 map을 int로 만들어주고 싶었다ㅎㅎ

 

마을"번호"붙이기지만, 마을의 번호 자체는 중요하지 않았다! 몇개의 마을이 있는지, 각 마을마다 몇집이 사는지만 중요했으므로 마을 인원수만 담은 벡터가 있어도 답을 낼 수 있었다.

---

DFS 풀이

void dfs(vector<vector<int>> *maps, int x, int y, int *people){
    int n = (*maps).size();
    vector<int> dx = {1, 0, -1, 0};
    vector<int> dy = {0, 1, 0, -1};
    for(int i = 0; i<4; i++){
        
        int newx = x + dx[i];
        int newy = y + dy[i];
        if(newx < 0 || newx >= n || newy <0 || newy >= n){
            continue;
        }
        if((*maps)[newx][newy] == 1){
            (*people)++;
            (*maps)[newx][newy] = 0;
            dfs(maps, newx, newy, people);
        }
    }
}

다른 문제 풀 때 작성했던 코드이다. DFS로 풀고자 한다면, 이렇게 함수를 따로 만들어서 해결해주면 된다!