[C/C++] 백준 17472번 - 다리 만들기 2 (삼성 A형 기출 문제)

 

<코드>

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

int N, M, ans;
int island_num; // 섬 개수
int map[11][11];
int visit[11][11];
int island_visit[7];
int parent[7];
int island[7][4]; // X1, X2, Y1, Y2
int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,1,-1 };
vector<tuple<int, int, int>> vec; // {거리, 섬1, 섬2}
vector<int> graph[7];
queue<int> q;

int find(int u)
{
	if (u == parent[u]) return u;
	else return find(parent[u]);
}

bool union_island(int u, int v)
{
	u = find(u);
	v = find(v);

	if (u != v)
	{
		// 노드 결합
		parent[u] = v;

		// 섬 간의 연결관계 기록
		graph[u].push_back(v);
		graph[v].push_back(u);
		return true;
	}
	else return false;
		
}

// 섬 번호 부여하기
void DFS(int x, int y)
{
	if (visit[x][y]) return;
	
	visit[x][y] = true; // 방문 표시
	map[x][y] = island_num; // 섬 번호

	island[island_num][0] = min(island[island_num][0], x); // X1 : x축 최소값
	island[island_num][1] = max(island[island_num][1], x); // X2 : x축 최대값
	island[island_num][2] = min(island[island_num][2], y); // Y1 : y축 최소값
	island[island_num][3] = max(island[island_num][3], y); // Y2 : y축 최대값

	for (int i = 0; i < 4; i++)
	{
		int next_x = x + dx[i];
		int next_y = y + dy[i];

		if (next_x >= 1 && next_x <= N && next_y >= 1 && next_y <= M)
		{
			if (map[next_x][next_y] != 0 && !visit[next_x][next_y])
				DFS(next_x, next_y);
		}
	}
}

// 섬 간의 최소거리 구하기
void distance(int now, int x, int y)
{
	for (int i = 0; i < 4; i++)
	{
		int now_x = x;
		int now_y = y;
		int dist = 0;

		while (true)
		{
			now_x += dx[i];
			now_y += dy[i];
			
			// 범위 이탈 또는 현재 섬일 경우 탈출
			if (now_x < 1 || now_x > N || now_y < 1 || now_y > M || map[now_x][now_y] == now) break;

			if (map[now_x][now_y] != 0)
			{
				// {거리, 출발한 섬, 도착한 섬} push
				vec.push_back({ dist , now, map[now_x][now_y] });
				break;
			}
			dist++;
		}
	}
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N >> M;

	// 초기 세팅
	for (int i = 1; i <= 6; i++)
		parent[i] = i; // 자기 자신을 부모로 지정

	// 섬 정보 입력받기
	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= M; j++)
			cin >> map[i][j];

	// 섬 번호 부여하기
	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= M; j++)
		{
			if (map[i][j] != 0)
			{
				if(!visit[i][j]) island_num++;
				DFS(i, j);
			}
		}

	// 섬 간의 거리 구하기
	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= M; j++)
		{
			if (map[i][j] != 0)
			{
				distance(map[i][j], i, j);
			}
		}

	sort(vec.begin(), vec.end());

	// MST 구하기
	for (int i = 0; i < vec.size(); i++)
	{
		int dist = get<0>(vec[i]);
		int island_1 = get<1>(vec[i]);
		int island_2 = get<2>(vec[i]);

		// 다리길이가 2미만이면 패스!
		if (dist < 2) continue;

		// 두 섬간의 다리 건설 시
		if (union_island(island_1, island_2))
			ans += dist;
	}

	// 섬이 모두 연결되어 있는지 확인
	int cnt = 1;
	q.push(1);

	while (!q.empty())
	{
		int now_island = q.front();
		q.pop();
		island_visit[now_island] = true;

		for (int i = 0; i < graph[now_island].size(); i++)
		{
			int next_island = graph[now_island][i];
			if (!island_visit[next_island])
			{
				q.push(next_island);
				cnt++;
			}
		}
	}

	if (cnt != island_num) cout << -1 << '\n';
	else cout << ans << '\n';
}

 

풀이 방법

 

저의 풀이에서는 위와 같이 X축과 Y축을 설정하였습니다.

코드가 좀 지저분해 보이지만 최대한 심플하고 깔끔하게 코딩을 해봤습니다.

 

<변수 설정>

parent 배열은 부모 자식 관계를 나타내고,

island 배열은 각 섬의 X, Y좌표의 최대, 최솟값들을 저장하였습니다.

 

예를 들어,

X1 = X좌표의 최솟값 = island[2][0] =  2 
X2 = X좌표의 최댓값 = island[2][1] =  4
Y1 = Y좌표의 최솟값 = island[2][2] =  1
Y2 = Y좌표의 최댓값 = island[2][3] =  2

2번 섬의 X 좌표의 최솟값, 최댓값은 각각 2와 4이고, Y 좌표의 최소값, 최대값은 각각 1과 2입니다.

 

그리고 vec 벡터는 출발 섬과 도착 섬 사이의 거리를 저장하는데,
{2, 2, 4}의 경우 2와 4번 섬 간의 거리가 2라는 의미입니다.

 

<풀이 알고리즘>

(1) DFS로 위와 같이 각 섬에 번호를 부여한다.

	// 섬 번호 부여하기
	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= M; j++)
		{
			if (map[i][j] != 0)
			{
				if(!visit[i][j]) island_num++;
				DFS(i, j);
			}
		}

// 섬 번호 부여하기
void DFS(int x, int y)
{
	if (visit[x][y]) return;
	
	visit[x][y] = true; // 방문 표시
	map[x][y] = island_num; // 섬 번호

	island[island_num][0] = min(island[island_num][0], x); // X1 : x축 최소값
	island[island_num][1] = max(island[island_num][1], x); // X2 : x축 최대값
	island[island_num][2] = min(island[island_num][2], y); // Y1 : y축 최소값
	island[island_num][3] = max(island[island_num][3], y); // Y2 : y축 최대값

	for (int i = 0; i < 4; i++)
	{
		int next_x = x + dx[i];
		int next_y = y + dy[i];

		if (next_x >= 1 && next_x <= N && next_y >= 1 && next_y <= M)
		{
			if (map[next_x][next_y] != 0 && !visit[next_x][next_y])
				DFS(next_x, next_y);
		}
	}
}

 

(2) 각 좌표에서 동서남북으로 각각 일자로 이동하면서 다른 섬에 도달하면 vec 벡터에 {거리, 출발 섬, 도착 섬}으로 push 해준다. (이동한 곳이 바다가 아닌 현재 섬이거나 범위를 이탈하면 루프를 탈출한다.)

// 섬 간의 최소거리 구하기
void distance(int now, int x, int y)
{
	for (int i = 0; i < 4; i++)
	{
		int now_x = x;
		int now_y = y;
		int dist = 0;

		while (true)
		{
			now_x += dx[i];
			now_y += dy[i];
			
			// 범위 이탈 또는 현재 섬일 경우 탈출
			if (now_x < 1 || now_x > N || now_y < 1 || now_y > M || map[now_x][now_y] == now) break;

			if (map[now_x][now_y] != 0)
			{
				// {거리, 출발한 섬, 도착한 섬} push
				vec.push_back({ dist , now, map[now_x][now_y] });
				break;
			}
			dist++;
		}
	}
}

 

(3) 크루스칼 알고리즘으로 MST(최소 스패닝 트리)를 만들어서 최소비용을 구한다.

	// MST 구하기
	for (int i = 0; i < vec.size(); i++)
	{
		int dist = get<0>(vec[i]);
		int island_1 = get<1>(vec[i]);
		int island_2 = get<2>(vec[i]);

		// 다리길이가 2미만이면 패스!
		if (dist < 2) continue;

		// 두 섬간의 다리 건설 시
		if (union_island(island_1, island_2))
			ans += dist;
	}

크루스칼 알고리즘 : 간선의 가중치가 작은 순서대로 노드들을 유니온 하면서 MST를 찾는 알고리즘 

 

(4) BFS로 1번 섬과 연결된 섬들의 수(1번 섬도 포함)를 구한 뒤 총섬의 개수(island_num)와 비교

	// 섬이 모두 연결되어 있는지 확인
	int cnt = 1;
	q.push(1);

	while (!q.empty())
	{
		int now_island = q.front();
		q.pop();
		island_visit[now_island] = true;

		for (int i = 0; i < graph[now_island].size(); i++)
		{
			int next_island = graph[now_island][i];
			if (!island_visit[next_island])
			{
				q.push(next_island);
				cnt++;
			}
		}
	}

	if (cnt != island_num) cout << -1 << '\n';
	else cout << ans << '\n';

 

 

 

www.acmicpc.net/problem/17472

17472번: 다리 만들기 2