글 읽기 - 맞았는데 생각해보니 왜 맞는지 이해가 안가요;

dmzld 3년 전 0

순수하게 혼자 작성한 코드인데요

도시 간 연결을 이차원 배열에 넣고

각각의 도시들을 순서대로 연결된 모든 도시들의 head 도시(유니온에서 가장 작은 도시)들과 비교하며

작은 도시 값으로 conn[도시] 값을 갱신합니다.

즉 1,2,4가 연결되있다면 conn[1,2,4] = 1인거죠

그런데 만약에 N = 4이고 (1,4) (2,4) (4,1) (4,2) 가 연결되었다고 주어질 때 ( conn[]의 초기 값은 0 )

conn을 갱신하는 밑에 표시해둔 알고리즘 상으로 결과가 conn[1 ~ 4] = { 0, 0, 3, 0 } 이라는 말도 안되는 값이 되어버리는데

왜 맞을까요??

#include <iostream>
#include <string>
#include <vector>

using namespace std;

int N, M, G[201][201], route[1000];
int conn[201] = { 0, };

int findParent(int n){
	int pN = conn[n];
	while (pN != conn[pN])
		pN = conn[pN];
	return pN;
}

bool arrive(){
	bool arrive = true;

	for (int i = 0; i < M - 1; i++)
		if (conn[route[i]] != conn[route[i + 1]]){
			arrive = false;
			break;
		}
	return arrive;
}

int main(){

	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N >> M;
	
	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= N; j++)
			cin >> G[i][j];

	for (int i = 0; i < M; i++)
		cin >> route[i];

    // 이 부분
	for (int i = 1; i <= N; i++){
		// head city of union is the smallest number city
		conn[i] = i;
		for (int j = 1; j <= N; j++){
			if (G[i][j] == 1){ 
				int p = findParent(j);
				conn[i] = conn[i] < p ? conn[i] : p;
			}
		}
	}
		
	if (arrive())
		cout << "YES";
	else
		cout << "NO";

	return 0;
}

dmzld 3년 전 0

제 생각엔 이렇게 고치는게 맞는 것 같은데

결과는 오히려 틀리다고 나오네요...

#include <iostream>
#include <string>
#include <vector>

using namespace std;

int N, M, G[201][201], route[1000];
int conn[201] = { 0, };

int findParent(int n){
	int pN = conn[n];
	while (pN != conn[pN])
		pN = conn[pN];
	return pN;
}

bool arrive(){
	bool arrive = true;

	for (int i = 0; i < M - 1; i++)
		if (conn[route[i]] != conn[route[i + 1]]){
			arrive = false;
			break;
		}
	return arrive;
}

int main(){

	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N >> M;
	
	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= N; j++)
			cin >> G[i][j];

	for (int i = 0; i < M; i++)
		cin >> route[i];

	for (int i = 1; i <= N; i++)
		conn[i] = i;

	for (int i = 1; i <= N; i++){
		// head city of union is the smallest number city
		for (int j = 1; j <= N; j++){
			if (G[i][j] == 1){ 
				int p = findParent(i),
					q = findParent(j);

				int h = p < q ? p : q;
				conn[i] = h;
				conn[j] = h;
			}
		}
	}
		
	if (arrive())
		cout << "YES";
	else
		cout << "NO";

	return 0;
}

sait2000 3년 전 1

왜 그렇냐면 둘 다 틀렸는데 데이터가 너무 약해서 그렇습니다. 연결을 따라서 가장 위에 있는 걸 찾았으면 가장 위에 있는 것끼리 이어야 합니다. 중간을 이으면 안 됩니다.

dmzld 3년 전 0

감사합니다

도착 가능 판별이랑 head 도시 갱신 부분 수정해서 납득 가능하게 맞았네요

#include <iostream>
#include <string>
#include <vector>

using namespace std;

int N, M, G[201][201], route[1000];
int conn[201] = { 0, };

int findHead(int n){
	int hN = conn[n];
	while (hN != conn[hN])
		hN = conn[hN];
	return hN;
}

bool arrive(){
	bool arrive = true;

	for (int i = 0; i < M - 1; i++)
		if (findHead(route[i]) != findHead(route[i + 1])){
			arrive = false;
			break;
		}
	return arrive;
}

int main(){

	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N >> M;
	
	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= N; j++)
			cin >> G[i][j];

	for (int i = 0; i < M; i++)
		cin >> route[i];

	for (int i = 1; i <= N; i++)
		conn[i] = i;

	for (int i = 1; i <= N; i++){
		// head city of union is the smallest number city
		for (int j = 1; j <= N; j++){
			if (G[i][j] == 1){ 
				int p = findHead(i),
					q = findHead(j);

                // connect head to head
				if (p < q) conn[q] = p;
				else conn[p] = q;
			}
		}
	}
		
	if (arrive())
		cout << "YES";
	else
		cout << "NO";

	return 0;
}

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

문제

문제

출처

ICPC

맞았는데 생각해보니 왜 맞는지 이해가 안가요;

dmzld 3년 전 0

dmzld 3년 전 0

sait2000 3년 전 1

dmzld 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말