네... 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; }}
이와 같이 코드를 작성했구요 예제의 경우는 통과하는데 제출후 테스트 케이스들중에서 만족을 못하는것같은데 왜 틀렸는지 모르겠어요 ㅠㅠ 다른사람들 코드도 봤는데 저랑 비슷하게 하셨던데 제껀 안되네요 ㅠ 고수분들의 도움이 필요합니다!
바른 질문이 답변을 끌어내실 수 있습니다.
질문하기를 통해서 질문하셔야 문제 번호가 붙게 되고요.
소스 코드 넣는 곳에 코드를 넣으셔야 코드 보기가 좋아서 답변을 얻으실 확율이 높습니다.
댓글을 작성하려면 로그인해야 합니다.
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;
}
}
이와 같이 코드를 작성했구요 예제의 경우는 통과하는데 제출후 테스트 케이스들중에서 만족을 못하는것같은데 왜 틀렸는지 모르겠어요 ㅠㅠ 다른사람들 코드도 봤는데 저랑 비슷하게 하셨던데 제껀 안되네요 ㅠ 고수분들의 도움이 필요합니다!