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

 

 

---

 

문제

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

 

 

개념

그래프, DFS, BFS

 

 

실행 결과

 

 

 

 

 

구현 코드(c++)

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

int g[25][25];
bool v[25][25];
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
int n;

int dfs(int x, int y) {
  int cnt = 1;
  v[x][y] = true;

  for (int i = 0; i < 4; i++) {
    int nx = x + dx[i], ny = y + dy[i];
    if (nx >= 0 && ny >= 0 && nx < n && ny < n && !v[nx][ny] &&
        g[nx][ny] == 1) {
      cnt += dfs(nx, ny);
    }
  }
  return cnt;
}

int main() {
  cin >> n;
  cin.ignore();

  for (int i = 0; i < n; i++) {
    string line;
    getline(cin, line);
    for (int j = 0; j < n; j++) {
      g[i][j] = line[j] - '0';  // 아스키 자동 변환
    }
  }

  vector<int> danzis;
  int cnt = 0;

  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      if (!v[i][j] && g[i][j] == 1) {
        int size = dfs(i, j);
        danzis.push_back(size);
        cnt++;
      }
    }
  }

  cout << cnt << "\n";
  sort(danzis.begin(), danzis.end());

  for (int i = 0; i < danzis.size(); i++) {
    cout << danzis[i] << "\n";
  }

  return 0;
}

 

 

 

 

코드 설명

1인 요소들끼리 묶기 위해서, 2차원 그래프에서 1로 묶을 수 있는 부분들을 탐색한다.

이때 방향벡터 dx와 dy를 선언하고, dfs를 활용하여 1로 구성된 단지들을 구해서 danzies 배열에 넣는다.

최종적으로 각 단지 배열의 개수를 각각 출력하도록 한다.

 

주의해야할 점은 입력 받을 때 띄어쓰기 없이 한 행을 그대로 입력받는다. ex. 0101011

따라서 string 헤더를 선언하고 getline으로 문자열 line을 입력받도록 한 후에, 해당 값에서 문자 '0'값을 빼서 자동으로 숫자로 변환하도록 해야 한다!

 

 

 

---