글 읽기 - 왜 틀린지 모르겠음.. (찾으면 3000원 계좌 입금해드림)

m29610928 3년 전 2

^{테스트 케이스 찾아본거 다 잘나왔는데 5%에서 틀렸습니다 나오네요..}

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

struct info{
	int x, y;
	info(int a, int b){
		x=a;
		y=b;
	}
};
struct Edge{
	int s, e, w;
	Edge(int a, int b, int c){
		s=a;
		e=b;
		w=c;
	}
};

int arr[11][11], unf[101];
int dx[4]={-1, 0, 1, 0};
int dy[4]={0, 1, 0, -1};
int n, m;
vector<Edge> v;

void Init(); 
void Union_bfs(); 
int getNum(int i, int j); 
bool Union(int a, int b); 
int Find(int v); 
void Connect_dfs();  
void DFS(int i, int j, int k, int step, int g);
int MST(); 
bool compare(Edge a, Edge b);

int main(void){
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	
	cin >> n >> m;
	Init();
	Union_bfs();
	Connect_dfs();
	cout << MST();
	
	return 0;
}

void Init(){
	for(int i=1; i<=n*m; i++){
		unf[i]=i;
	}
	for(int i=0; i<n; i++){
		for(int j=0; j<m; j++){
			int bit;
			cin >> bit;
			if(bit==1) arr[i][j]=1;
			else arr[i][j]=0;
		}
	}
}

void Union_bfs(){
	bool visited[n][m]={false, };
	queue<info> q;
	
	for(int i=0; i<n; i++){
		for(int j=0; j<m; j++){
			if(arr[i][j]==1){
				q.push(info(i, j));
				visited[i][j] = true;
				while(!q.empty()){
					int x = q.front().x;
					int y = q.front().y;
					
					q.pop();
					for(int i=0; i<4; i++){
						int nx = x + dx[i];
						int ny = y + dy[i];
						if(nx<0 || ny<0 || nx>=n || ny>=m) continue;
						if(arr[nx][ny]==1 && !visited[nx][ny]){
							q.push(info(nx, ny));
							visited[nx][ny] = true;
							Union(getNum(x, y), getNum(nx, ny));
						}
					}
				}
			}
		}
	}
}

int getNum(int i, int j){
	return (i*m) + j + 1;	
}

bool Union(int a, int b){
	int fa = Find(a);
	int fb = Find(b);
	if(fa!=fb) {
		unf[fa] = b;	
		return true;
	}
	else return false;
}

int Find(int v){
	if(unf[v]==v) return v;
	else return Find(unf[v]);
}

void Connect_dfs(){
	for(int i=0; i<n; i++){
		for(int j=0; j<m; j++){
			if(arr[i][j]==1){
				for(int k=0; k<4; k++){
					int nx = i + dx[k];
					int ny = j + dy[k];
					if(arr[nx][ny]==0) DFS(nx, ny, k, 0, Find(getNum(i, j)));
				}
			}
		}
	}
}

void DFS(int x, int y, int k, int step, int g){
	if(x<0 || y<0 || x>=n || y>=m) return;
	if(arr[x][y]==1){
		if(step<2) return;
		else{
			v.push_back(Edge(g, Find(getNum(x, y)), step));
			return;	
		}
	}
	DFS(x+dx[k], y+dy[k], k, step+1, g);
	return;		
}

int MST(){
	int sum=0, temp=-1;
	bool flag=true;
	
	sort(v.begin(), v.end(), compare);
	for(int i=0; i<v.size(); i++){
		int s = v[i].s;
		int e = v[i].e;
		int w = v[i].w;
		if(Union(s, e)) sum+=w; 
	}
	for(int i=0; i<n; i++){
		for(int j=0; j<m; j++){
			if(arr[i][j]==1){
				temp = Find(getNum(i, j));
				break;
			}
		}
	}
	for(int i=0; i<n; i++){
		for(int j=0; j<m; j++){
			if(arr[i][j]==1){
				if(temp!=Find(getNum(i, j))) flag=false;
			}
		}
	}
	if(flag) return sum;
	else return -1;
}

bool compare(Edge a, Edge b){
	if(a.w<b.w) return true;
	else return false;
}

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

문제

문제

출처

ICPC

왜 틀린지 모르겠음.. (찾으면 3000원 계좌 입금해드림)

m29610928 3년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말