BOJ 1976 여행 가자 (C++)

 

슬슬 기초에서 좀 더 나아간 문제를 풀어보아야겠다 싶어서 풀어봤다. 

문제 자체는 Union Find를 알고 있다면 어렵지 않은 문제같다. 

사실 그게 아니더라도 도시별 그룹을 어떻게 만들것인지  어떻게 설계하냐에 따라 어떻게든 풀 수 있을 듯 하다.

이 문제는 합치는것만 있고 분리할 일이 없으므로(도로가 끊기는 등의 옵션) 유니온 파인드를 쓰면 될 것 같다는 생각을 했고 index헷갈림 문제로 몇번 실패했으나 금방 성공하였다. 

최대한 include 없이 풀어보고싶은데 이정도 난이도는 없이도 풀 수 있을 것 같은데 더 어려운 것도 가능하게 되도록 연습해야겠다. 

#define _CRT_SECURE_NO_WARNINGS
#include    <iostream>
using namespace std;

int all_city[200]; // index는 도시 번호, 값은 부모 도시 번호

int find_root_city(int city_num) //입력은 노드 번호, 출력은 노드의 부모 번호, root city num을 찾는다 
{
	if (city_num == all_city[city_num]) // 도시 번호와 부모 도시 번호가 같다면 root citi num
	{
		return city_num;
	}
	else
	{
		return (all_city[city_num] = find_root_city(all_city[city_num])); // 다르다면 연결되어있으므로 연결 확인 (부모가 있음, 부모가root인지 확인)
	}
}

void union_city(int city1, int city2) // 두 city merge
{
	int root_city1 = find_root_city(city1);
	int root_city2 = find_root_city(city2);

	if (root_city1 == root_city2)
	{
		return;
	}

	all_city[root_city2] = root_city1;  // city2의 부모가 city1이 된다.
}

int main()
{
	int N, M;
	scanf("%d", &N);
	scanf("%d", &M);
	int** line;
	line = (int**)malloc(sizeof(int*)*(N+1));
	for (int i = 1; i <= N; ++i) // 1부터 해줘야 이후 visit city와 헷갈리지 않을 듯 함
	{
		line[i] = (int*)malloc(sizeof(int)*(N+1));
		all_city[i] = i; // 값 초기화 해줘야 함, 모든 city의 root city는 자기자신으로 초기화
		for (int j = 1; j <= N; ++j)
		{
			scanf("%d", &line[i][j]);
		}
	}

	int* visit_city = (int*)malloc(sizeof(int)*M);
	for (int i = 0; i < M; ++i)
	{
		scanf("%d", &visit_city[i]);
	}

	//합체 
	for (int i = 1; i <= N; ++i)
	{
		for (int j = 1; j <= N; ++j)
		{
			if (line[i][j] == 1) //연결되어있다면 
			{
				union_city(i, j); //i번 city, j번 city 연결
			}
		}
	}

	int same_way = find_root_city(visit_city[0]);
	for (int i = 1; i < M; ++i)
	{
		if (same_way != find_root_city(visit_city[i])) // 연결되어있다면 root city num이 동일해야 함
		{
			printf("NO");
			return 0;
		}
	}
	printf("YES");
	return 0;
}