xorb114   6년 전

네... DFS 초보입니다...


#include <iostream>

#include <cstdio>

#include <vector>
#include <algorithm>

using namespace std;

int N, components, cnt;
vector<int> res;
char arr[26][26];
bool visited[26][26];
int x_move[4] = {0,0,1,-1};
int y_move[4] = {1,-1,0,0};

void DFS(int x, int y) {
  cnt ++;
  visited[x][y] = true;
  for(int i=0 ; i<4; i++) {
    int x_next = x+x_move[i];
    int y_next = y+y_move[i];
    if(x_next>=0 && x_next<N && y_next>=0 && y_next<N){
      if(!visited[x_next][y_next] && arr[x_next][y_next]=='1') {
        DFS(x_next, y_next);
      }
    }
  }
}

void Search() {
  for (int i =0 ; i < N; i++) {
    for(int j = 0 ; j < N; j++) {
      if(!visited[i][j] && arr[i][j]=='1') {
        components++;
        DFS(i, j);
        res.push_back(cnt);
        cnt = 0;
      }
    }
  }
}

void init() {
  components = 0;
  cnt = 0;
  for(int i = 0; i< 26; i ++) {
    for(int j = 0 ; j< 26; j++) {
      arr[i][j] = '0';
      visited[i][j] = false;
    }
  }
}

int main (){
  ios_base::sync_with_stdio(false);
  cin.tie(0);

  init();
  cin >> N;

  for(int i = 0; i< N; i++) {
    scanf("%s", arr[i]);
  }
  Search();
  sort(res.begin(), res.end());
  cout << components << endl;
  for(int i = 0; i < (int)res.size(); i++) {
    cout << res[i] << endl;
  }
}

이와 같이 코드를 작성했구요 예제의 경우는 통과하는데 제출후 테스트 케이스들중에서 만족을 못하는것같은데 왜 틀렸는지 모르겠어요 ㅠㅠ 다른사람들 코드도 봤는데 저랑 비슷하게 하셨던데 제껀 안되네요 ㅠ 고수분들의 도움이 필요합니다!

sgchoi5   6년 전

바른 질문이 답변을 끌어내실 수 있습니다.

질문하기를 통해서 질문하셔야 문제 번호가 붙게 되고요.

소스 코드 넣는 곳에 코드를 넣으셔야 코드 보기가 좋아서 답변을 얻으실 확율이 높습니다.

댓글을 작성하려면 로그인해야 합니다.