백준 17472번 다리 만들기 2

문제 링크입니다: https://www.acmicpc.net/problem/17472

17472번: 다리 만들기 2

다리의 방향도 고려해야하기 때문에 생각보다 까다로운 시뮬레이션 문제였습니다.

코드를 깔끔하게 짠다고 노력했는데도 불구하고 상당히 지저분하기 때문에 주석을 최대한 꼼꼼하게 달았습니다.

 

알고리즘은 아래와 같습니다.

1. 섬으로 표기된 지역 즉, 1로 표시된 좌표를 모두 islands 벡터에 추가해줍니다.

2. islands 벡터에 있는 좌표를 순차적으로 확인하며 아래 혹은 오른쪽 혹은 양방향으로 다리를 배치해줍니다.

2.1 이 때, 아래와 오른쪽으로만 다리를 배치하는 이유는 좌표를 좌상단부터 우하단 순으로 입력을 받았고 islands 벡터에도 동일한 순서대로 좌표가 추가되어있기 때문에 반대 방향을 확인할 필요가 없습니다. (반대방향으로 다리를 놓을 수 있을 경우 이미 전 좌표에서 다리를 배치했을 것이라고 그리디하게 판단합니다.)

3. isAllVisited 함수를 통해 모든 섬이 연결되어 있는지 확인하고 만약 모든 섬이 연결되어 있다면 result를 업데이트해줍니다.

 

	#include <iostream>
	#include <vector>
	#include <algorithm>
	#include <queue>
	using namespace std;
	const int MAX = 10;
	const int INF = 987654321;
	typedef struct
	{
	int y, x;
	}Dir;
	Dir moveDir[4] = { { 1, 0 },{ 0, 1 },{ -1, 0 },{ 0, -1 } };
	typedef struct
	{
	int y, x, dir;
	}State;
	int N, M;
	int result;
	int sea[MAX][MAX];
	vector<pair<int, int>> islands;
	bool isAllConnected(int tempSea[][MAX])
	{
	queue<State> q;
	q.push({ islands[0].first, islands[0].second, 0 });
	bool visited[MAX][MAX] = { false, };
	visited[islands[0].first][islands[0].second] = true;
	// 다리 visited 배열: {y, x, 가로/세로}
	bool bridgeVisited[MAX][MAX][2] = { false, };
	// BFS 알고리즘을 통해 모든 섬이 연결되어 있는지 확인
	while (!q.empty())
	{
	int y = q.front().y;
	int x = q.front().x;
	int dir = q.front().dir;
	q.pop();
	// 다리일 경우 그 방향으로만 전진
	if (tempSea[y][x] >= 2)
	{
	int nextY = y + moveDir[dir].y;
	int nextX = x + moveDir[dir].x;
	// 섬이고 이미 방문한 지역일 경우
	if (visited[nextY][nextX])
	{
	continue;
	}
	// 삼항 연산자는 방향 상관없이 가로 세로만을 확인하기 위해
	bridgeVisited[nextY][nextX][dir >= 2 ? 3 - dir : dir] = true;
	if (tempSea[nextY][nextX] == 1)
	{
	visited[nextY][nextX] = true;
	}
	q.push({ nextY, nextX, dir });
	continue;
	}
	// 섬일 경우에는 동서남북 다 확인
	// 가로 세로
	for (int k = 0; k < 2; k++)
	{
	// 방향
	for (int j = 0; j < 2; j++)
	{
	int nextY = j == 0 ? y + moveDir[k].y : y - moveDir[k].y;
	int nextX = j == 0 ? x + moveDir[k].x : x - moveDir[k].x;
	// 경계를 벗어날 경우
	if (nextY < 0 || nextY >= N || nextX < 0 || nextX >= M)
	{
	continue;
	}
	// 바다이거나 이미 방문한 지역
	if (tempSea[nextY][nextX] == 0 || visited[nextY][nextX])
	{
	continue;
	}
	// 다리인데 방향이 맞지 않은 경우
	if (tempSea[nextY][nextX] >= 2 && (tempSea[nextY][nextX] & (1 << (k + 1))) == false)
	{
	continue;
	}
	// 다리이고 같은 방향이지만 이미 방문한 다리
	if (tempSea[nextY][nextX] >= 2 && bridgeVisited[nextY][nextX][k])
	{
	continue;
	}
	if (tempSea[nextY][nextX] >= 2)
	{
	bridgeVisited[nextY][nextX][k] = true;
	}
	if (tempSea[nextY][nextX] == 1)
	{
	visited[nextY][nextX] = true;
	}
	q.push({ nextY, nextX, k + j * 2 });
	}
	}
	}
	// islands 벡터에 포함된 모든 섬을 방문해야지만 true를 반환
	for (int i = 0; i < islands.size(); i++)
	{
	if (visited[islands[i].first][islands[i].second] == false)
	{
	return false;
	}
	}
	return true;
	}
	// 매개변수: 이차원 배열, 다리를 배치하기 시작할 섬 인덱스, 현재까지 배치한 다리의 길이
	void func(int tempSea[][MAX], int idx, int bridgeLength)
	{
	// 섬들이 모두 연결되어 있다면 result 업데이트
	if (isAllConnected(tempSea))
	{
	result = min(result, bridgeLength);
	return;
	}
	for (int i = idx; i < islands.size(); i++)
	{
	// ↓ 방향과 → 방향으로 하나의 다리를 성공적으로 배치했을 경우 재귀함수 호출
	for (int k = 0; k < 2; k++)
	{
	int y = islands[i].first;
	int x = islands[i].second;
	int tempY = y;
	int tempX = x;
	int cnt = 0;
	bool flag = false;
	int temp[MAX][MAX];
	// 하나의 방향으로만 다리를 배치하기 위해
	// for문을 돌 때마다 tempSea 이차원 배열 복사
	for (int n = 0; n < N; n++)
	{
	for (int m = 0; m < M; m++)
	{
	temp[n][m] = tempSea[n][m];
	}
	}
	// 경계를 벗어나거나 다른 섬에 도달할 때까지 while문
	while (1)
	{
	int nextY = y + moveDir[k].y;
	int nextX = x + moveDir[k].x;
	if (nextY < 0 || nextY >= N || nextX < 0 || nextX >= M)
	{
	break;
	}
	if (temp[nextY][nextX] == 1)
	{
	flag = true;
	break;
	}
	// 다리의 방향이 겹칠 수 있기 때문에 비트 마스킹으로 표기
	// ↓: 2, →: 4, 양방향 다: 6
	temp[nextY][nextX] |= (1 << (k + 1));
	y = nextY;
	x = nextX;
	cnt++;
	}
	// 섬에 도달했고 배치한 다리의 길이가 2 이상인 경우 재귀함수 호출
	if (flag && cnt > 1)
	{
	func(temp, i + 1, bridgeLength + cnt);
	}
	}
	// 모든 방향으로 성공적으로 다리를 배치했을 경우 재귀함수 호출
	bool flags[2] = { false, };
	int cnts[2] = { 0, };
	int temp[MAX][MAX];
	for (int n = 0; n < N; n++)
	{
	for (int m = 0; m < M; m++)
	{
	temp[n][m] = tempSea[n][m];
	}
	}
	for (int k = 0; k < 2; k++)
	{
	int y = islands[i].first;
	int x = islands[i].second;
	int tempY = y;
	int tempX = x;
	flags[k] = false;
	cnts[k] = 0;
	while (1)
	{
	int nextY = y + moveDir[k].y;
	int nextX = x + moveDir[k].x;
	if (nextY < 0 || nextY >= N || nextX < 0 || nextX >= M)
	{
	break;
	}
	if (temp[nextY][nextX] == 1)
	{
	flags[k] = true;
	break;
	}
	temp[nextY][nextX] |= (1 << (k + 1));
	y = nextY;
	x = nextX;
	cnts[k]++;
	}
	if ((flags[k] && cnts[k] > 1) == false)
	{
	break;
	}
	}
	if (flags[0] && flags[1] && cnts[0] > 1 && cnts[1] > 1)
	{
	func(temp, i + 1, bridgeLength + cnts[0] + cnts[1]);
	}
	}
	}
	int main(void)
	{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> N >> M;
	for (int i = 0; i < N; i++)
	{
	for (int j = 0; j < M; j++)
	{
	cin >> sea[i][j];
	if (sea[i][j])
	{
	islands.push_back({ i, j });
	}
	}
	}
	result = INF;
	func(sea, 0, 0);
	if (result == INF)
	{
	cout << -1 << "\n";
	}
	else
	{
	cout << result << "\n";
	}
	return 0;
	}

view raw .cpp hosted with ❤ by GitHub

개발환경:Visual Studio 2019

 

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~