글 읽기 - 11%에서 틀렸다고 합니다.

haejun0317 4년 전 0

안녕하세요. 질문 요청드립니다.

MST로 풀었는데, 11%에서 틀렸다고 나옵니다.. 질문에 있는 반례, 샘플케이스 모두 잘 나옵니다 ㅠㅠ..

1. 섬에 번호 매기기 작업

+ 번호 매기면서 Coor 구조체 배열에 섬에 칸 정보저장(y,x,섬번호)

2. Coor구조체 배열에 저장된 칸 정보를 4방면으로 다리를 지을 수 있는지 확인

3. MST

2번 작업에서 다리 2개 이상시 연결되는 부분 확인했고,

3번 작업에서도 MST 정상적으로 작동하는 거 확인했습니다.

어떤 부분에서 틀렸는지 질문 드립니다 ㅠㅠ 감사합니다.

#include<iostream>
#include<vector>
#include<queue>
#include<memory.h>
#include<algorithm>
using namespace std;
const int MAX = 13;
int arr[MAX][MAX];
int check[MAX][MAX];

int n, m;

int ans = 0;

//4방면 체크 함수
bool inside(int y, int x) {
	return y >= 0 && y < n && x >= 0 && x < m;
}
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };

//좌표 구조체, 큐
struct coor {
	int y;
	int x;
	int num;
};
queue <coor> q;
//섬 번호 카운트
int sumCnt = 1;

// 2번 과정을 진행할 구조체 (y,x,num 정보저장)
coor Coor[1002];
int CoorCnt = 0;

// 3번 MST과정을 위한 간선을 저장할 벡터 생성
vector <pair<int, pair<int, int>>> v;
// 점은 sumCnt -1 선은 e;
int e = 0;
//parent 함수
int parent[105];
int parentCheck[105];

// 1. 섬에 번호 매길 bfs();
void bfs() {
	while (!q.empty()) {
		int y = q.front().y;
		int x = q.front().x;
		int num = q.front().num;
		q.pop();
		check[y][x] = 1;
		arr[y][x] = num;

		Coor[CoorCnt].y = y;
		Coor[CoorCnt].x = x;
		Coor[CoorCnt].num = num;
		CoorCnt++;

		int ny, nx;
		for (int i = 0; i < 4; i++) {
			ny = y + dy[i];
			nx = x + dx[i];
			if (inside(ny, nx) && check[ny][nx] == 0 && arr[ny][nx] == 1) {
				check[ny][nx] = 1;
				q.push({ ny,nx,num });
			}
		}
	}
}

// 2. 연결된 간선 확인 작업 top, bottom, left, right();
void top(int y, int x, int num) {
	int cnt = 0;
	for (int i = y - 1; i >= 0; i--) {
		if (arr[i][x] != num) {
			if (arr[i][x] == 0) {
				cnt++;
				continue;
			}
			else {
				if (cnt >= 2) {
					v.push_back(make_pair(cnt, make_pair(num, arr[i][x])));
					return;
				}
				else return;
			}
		}
		else return;
	}
}
void bottom(int y, int x, int num) {
	int cnt = 0;
	for (int i = y + 1; i < n; i++) {
		if (arr[i][x] != num) {
			if (arr[i][x] == 0) {
				cnt++;
				continue;
			}
			else {
				if (cnt >= 2) {
					v.push_back(make_pair(cnt, make_pair(num, arr[i][x])));
					return;
				}
				else return;
			}
		}
		else return;
	}
}
void left(int y, int x, int num) {
	int cnt = 0;
	for (int i = x - 1; i >= 0; i--) {
		if (arr[y][i] != num) {
			if (arr[y][i] == 0) {
				cnt++;
				continue;
			}
			else {
				if (cnt >= 2) {
					v.push_back(make_pair(cnt, make_pair(num, arr[y][i])));
					return;
				}
				else return;
			}
		}
		else return;
	}
}
void right(int y, int x, int num) {
	int cnt = 0;
	for (int i = x + 1; i < m; i++) {
		if (arr[y][i] != num) {
			if (arr[y][i] == 0) {
				cnt++;
				continue;
			}
			else {
				if (cnt >= 2) {
					v.push_back(make_pair(cnt, make_pair(num, arr[y][i])));
					return;
				}
				else return;
			}
		}
		else return;
	}
}

// 3. MST작업
int find(int x) {
	if (parent[x] == x) return x;
	else return parent[x] = find(parent[x]);
}

void Union(int a, int b) {
	a = find(a);
	b = find(b);
	parent[a] = b;
}

bool sameparent(int a, int b) {
	a = find(a);
	b = find(b);
	if (a != b) return false;
	else return true;
}

int main() {

	ios_base::sync_with_stdio(0);
	cin.tie(NULL); cout.tie(NULL);

	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> arr[i][j];
		}
	}

	// 1번 섬에 번호 매기기 작업 (ok)
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (arr[i][j] == 1 && check[i][j] == 0) {
				q.push({ i,j,sumCnt });
				bfs();
				sumCnt++;
			}
		}
	}

	// 2번 구조체 배열 CoorCnt까지 반복하면서 연결된 부분 확인
	for (int i = 0; i < CoorCnt; i++) {
		//상
		top(Coor[i].y, Coor[i].x, Coor[i].num);
		//하
		bottom(Coor[i].y, Coor[i].x, Coor[i].num);
		//좌
		left(Coor[i].y, Coor[i].x, Coor[i].num);
		//우
		right(Coor[i].y, Coor[i].x, Coor[i].num);
	}

	// 3. MST 작업
	for (int i = 0; i < sumCnt; i++) {
		parent[i] = i;
	}

	//check함수 재활용
	sort(v.begin(), v.end());
	for (int i = 0; i < v.size(); i++) {
		if (sameparent(v[i].second.first, v[i].second.second) == false) {
			Union(v[i].second.first, v[i].second.second);
			ans += v[i].first;
		}
	}

	int flag = 0;
	int tempa = parent[1];
	for (int i = 1; i < sumCnt; i++) {
		parent[i] = find(i);
	}
	//부모가 다른지 확인, 다르면 flag = -1
	for (int i = 1; i < sumCnt; i++) {
		if (parent[i] != tempa) flag = 1;
	}

	//정답
	if (ans == 0 || flag == 1) cout << -1;
	else cout << ans;


	// 확인 하는 부분
	/*
	cout << endl;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cout << arr[i][j] << " ";
		}
		cout << endl;
	}


	for (int i = 0; i < v.size(); i++) {
		cout << v[i].second.first << " -> " << v[i].second.second << " ::: " << v[i].first << endl;
	}
	*/



	return 0;
}

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

문제

문제

출처

ICPC

11%에서 틀렸다고 합니다.

haejun0317 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말