BOJ/백준 - 2667 단지번호붙이기 C++

1. string으로 받아가면서 2차원 배열에 넣고

2. 방문하지 않았고 map[i][j]==1이라면 dfs/bfs 호출

int dx[4] = { 0,0,-1,1 };

int dy[4] = { 1,-1,0,0 };

이 배열의 의미는 상,하,좌,우이다.

 

가운데 점이 현재 위치이라고 했을 때, 현재 기준에서

상 0,1 = dx[0],dy[0]

하 0,-1 = dx[1],dy[1]

좌 -1,0 = dx[2],dy[2]

우 1,0 = dx[3],dy[3]

3. cnt로 집의 갯수를 세고, 오름차순으로 정렬 후 답 출력

 

1. dfs로 푼 것.

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
 
#define MAX 25
using namespace std;
 
int N;
 
int map[MAX][MAX];
int visit[MAX][MAX];
 
int dx[4] = { 0,0,-1,1 };
int dy[4] = { 1,-1,0,0 };
int cnt;
vector<int> house_cnt;
 
void dfs(int x, int y) {
    cnt++;
    visit[x][y] = 1;
 
    for (int i = 0; i < 4; i++) {
        int nxtx = x + dx[i];
        int nxty = y + dy[i];
 
        if (nxtx < 0 || nxtx >= N || nxty >= N || nxty < 0) continue;
        if (map[nxtx][nxty] == 1 && visit[nxtx][nxty] == 0) dfs(nxtx, nxty);
    }
}
 
 
int main(void) {
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
 
    cin >> N;
 
    string str;
 
    for (int i = 0; i < N; i++) {
        cin >> str;
        for (int j = 0; j < N; j++) {
            map[i][j] = str[j] - '0';
        }
    }
 
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (visit[i][j] == 0 && map[i][j] == 1) {
                cnt = 0;
                dfs(i, j);
                house_cnt.push_back(cnt);
            }
        }
    }
 
    sort(house_cnt.begin(), house_cnt.end());
    int ans = house_cnt.size();
    cout << ans << "\n";
    for (int i = 0; i < ans; i++) {
        cout << house_cnt[i] << '\n';
    }
 
    return 0;
}
 

 

 

2. bfs로 푼 것

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
 
#define MAX 25
using namespace std;
 
int N;
 
int map[MAX][MAX];
int visit[MAX][MAX];
 
int dx[4] = { 0,0,-1,1 };
int dy[4] = { 1,-1,0,0 };
int cnt;
vector<int> house_cnt;
 
 
void bfs(int x, int y) {
    queue<pair<int, int>>q;;
    q.push({ x,y });
    visit[x][y] = 1;
    cnt++;
 
    while (!q.empty()) {
        //현재 x,y
        int curx = q.front().first;
        int cury = q.front().second;
        q.pop();
 
        //상, 하, 좌, 우
        for (int i = 0; i < 4; i++) {
            int nxtx = curx + dx[i];
            int nxty = cury + dy[i];
 
            //범위 확인
            if (nxtx < 0 || nxtx >= N || nxty < 0 || nxty >= N) continue;
            
            //방문한 적 없고, map에서 1이라면 bfs
            if (visit[nxtx][nxty] == 0 && map[nxtx][nxty] == 1) bfs(nxtx, nxty);
        }
    }
}
 
 
int main(void) {
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
 
    cin >> N;
 
    string str;
 
    for (int i = 0; i < N; i++) {
        cin >> str;
        for (int j = 0; j < N; j++) {
            map[i][j] = str[j] - '0';
        }
    }
 
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (visit[i][j] == 0 && map[i][j] == 1) {
                cnt = 0;
                bfs(i, j);
                house_cnt.push_back(cnt);
            }
        }
    }
 
    sort(house_cnt.begin(), house_cnt.end());
    int ans = house_cnt.size();
    cout << ans << "\n";
    for (int i = 0; i < ans; i++) {
        cout << house_cnt[i] << '\n';
    }
 
    return 0;
}
 

 

 

 

 

+) 두번째 풀었을 때 답

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int const MAX = 26;
char home[MAX][MAX];
int visit[MAX][MAX];
int N;
int dr[] = { 0,0,1,-1};
int dc[] = { 1,-1,0,0 };
int cnt;
vector<int> result;
 
 
bool valid(int r, int c) {
    if (r >= N || c >= N || r < 0 || c < 0) {
        return false;
    }
    return true;
}
 
void dfs(int r, int c) {
    visit[r][c] = 1;
    cnt++;
 
    for (int i = 0; i < 4; i++) {
        int nextr = r+dr[i];
        int nextc = c+dc[i];
        if (valid(nextr, nextc) && home[nextr][nextc]=='1' && !visit[nextr][nextc]) {
            dfs(nextr, nextc);
        }
    }
}
int main() {
 
    cin >> N;
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> home[i][j];
        }
    }
    
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (home[i][j] == '1' && visit[i][j]==0) {
                cnt = 0;
                dfs(i, j);
                result.push_back(cnt);
            }
        }
    }
 
    sort(result.begin(), result.end());
 
 
    int len = result.size();
    cout << len << '\n';
    for (int i = 0; i < len; i++) {
        cout << result[i] << '\n';
    }
    return 0;
}