U E D R , A S I H C RSS

1R/2016_09_14



1. 오늘의 문제

2. 참가자

  • 박인서

3. 코드

3.1. 15이원준

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int arr[27][27] = { 0, };
int N, num = 0;
vector<int> v;

void search(int i, int j) {
	v[num]++;
	arr[i][j] = -1;
	if(arr[i+1][j] == 1)
		search(i + 1, j);
	if(arr[i-1][j] == 1)
		search(i - 1, j);
	if(arr[i][j+1] == 1)
		search(i, j + 1);
	if(arr[i][j-1] == 1)
		search(i, j - 1);
}

int main() {
	cin >> N;
	for (int i = 0; i<27; i++) {
		for (int j = 0; j<27; j++) {
			arr[i][j] = 0;
		}
	}

	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			int tmp;
			scanf("%1d", &tmp);
			arr[i][j] = tmp;
		}
	}
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			if (arr[i][j] == 1) {
				v.push_back(0);
				search(i, j);
				num++;
			}
		}
	}
	sort(v.begin(), v.end());
  cout<<v.size()<<endl;
	for (int i = 0; i<v.size(); i++) {
		cout << v[i] << endl;
	}
}

3.2. 박인서

#include <iostream>
#include <vector>
#include <algorithm>
char a[30][30];
bool visit[30][30];
int n;
std::vector<int> res;
 
int dfs (int i,int j){
    int cnt=1;
    visit[i][j]=true;
     
    if (i!=1 && a[i-1][j]=='1' && !visit[i-1][j])
        cnt+=dfs(i-1,j);
    if (i!=n && a[i+1][j]=='1' && !visit[i+1][j])
        cnt+=dfs(i+1,j);
    if (j!=1 && a[i][j-1]=='1' && !visit[i][j-1])
        cnt+=dfs(i,j-1);
    if (j!=n && a[i][j+1]=='1' && !visit[i][j+1])
        cnt+=dfs(i,j+1);
         
    return cnt;
}
 
int main (){
    std::cin>>n;
    for (int i=1;i<=n;i++){
        for (int j=1;j<=n;j++){
            std::cin>>a[i][j];
        }
    }
     
     
    for (int i=1;i<=n;i++){
        for (int j=1;j<=n;j++){
            if (a[i][j]=='1' && !visit[i][j])
                res.push_back(dfs(i,j));
        }
    }
     
    std::cout<<res.size()<<std::endl;
    std::sort(res.begin(),res.end());
    for(int i=0;i<res.size();i++)
        std::cout<<res[i]<<std::endl;
     
    return 0;
}

3.3. 곽정흠


4. 아이디어

4.1. 15이원준


4.2. 박인서

  • 단지 중 1곳 파악->단지 완전 탐색 순서로 단지를 탐색하면 된다

4.3. 곽정흠

Valid XHTML 1.0! Valid CSS! powered by MoniWiki
last modified 2021-02-07 05:22:06
Processing time 0.0269 sec