[BOJ]2146번: 다리 만들기 (c++)

 

https://www.acmicpc.net/problem/2146

2146번: 다리 만들기

 

 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

int dir_x[4] = { 0, 1, 0, -1 };
int dir_y[4] = { 1, 0, -1, 0 };
enum {BOUNDARY = 0, MAX = 100};

struct info {
	int island, cost;
};

// map 범위 내인지 검사
bool reachable(vector<vector<int>>& map, int x, int y)
{
	int N = map.size();
	return !(x < 0 || x >= N || y < 0 || y >= N);
}

// 섬에 대한 정보를 너비우선 탐색으로 체크하며 저장한다.
void bfs_island(vector<vector<int>>& map, vector<vector<info>>& cost_map, queue<pair<int, int>> &q, int island_idx)
{
	while (!q.empty())
	{
		int q_x = q.front().first;
		int q_y = q.front().second;
		q.pop();

		// 4방향 탐색
		for (int i = 0; i < 4; ++i)
		{
			int n_x = q_x + dir_x[i];
			int n_y = q_y + dir_y[i];

			// 다음 지점이 map 범위 내이고, 아직 섬 정보를 입력하기 전이면
			if (reachable(map, n_x, n_y) && cost_map[n_x][n_y].island == 0)
			{
				// 다음 지점이 섬일 때
				if (map[n_x][n_y] == 1)
				{
					cost_map[n_x][n_y].island = island_idx;
					q.push({n_x, n_y});
				}
				/*
					다음 지점이 바다일 때 
					= 현재 지점은 섬의 경계선이므로, 현재 지점의 거리값을 0으로 저장 
				*/
				else
				{
					cost_map[q_x][q_y].cost = BOUNDARY;
				}
			}
		}
	}
}

// 섬으로부터의 거리를 너비우선탐색으로 저장하며 섬과 섬 사이의 최소거리를 구한다.
int bfs_bridge(vector<vector<int>>& map,vector<vector<info>> &cost_map, queue<pair<int, int>> &q)
{
	int min_cost = MAX * MAX;

	while (!q.empty())
	{
		int q_x = q.front().first;
		int q_y = q.front().second;
		int this_island = cost_map[q_x][q_y].island;
		int this_cost = cost_map[q_x][q_y].cost;
		q.pop();

		// 4방향 탐색
		for (int i = 0; i < 4; ++i)
		{
			int n_x = q_x + dir_x[i];
			int n_y = q_y + dir_y[i];

			// 다음 지점이 map의 범위 내에 있고
			if (reachable(map, n_x, n_y))
			{
				// 다음 지점에 아직 섬 정보가 저장되지 않았다면 
				if (cost_map[n_x][n_y].island == 0)
				{
					cost_map[n_x][n_y].island = this_island;
					cost_map[n_x][n_y].cost = this_cost + 1;
					q.push({ n_x, n_y });
				}
				// 다음 지점의 섬 정보가 현재 지점과 다른 섬이라면 거리 최소값 갱신
				else if (cost_map[n_x][n_y].island != this_island)
				{
					min_cost = min(this_cost + cost_map[n_x][n_y].cost, min_cost);
				}
			}
		}
	}
	return min_cost;
}

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

	// 입력
	int N;
	cin >> N;
	vector<vector<int>> map(N, vector<int>(N));
	for (int i = 0; i < N; ++i)
	{
		for (int j = 0; j < N; ++j)
		{
			cin >> map[i][j];
		}
	}

	// {섬 넘버, 섬으로부터 떨어진 거리}를 저장할 벡터
	vector<vector<info>> cost_map(N, vector<info>(N, {0, -1}));
	queue<pair<int, int>> q;
	
	/*
		map 전체를 순회하며 섬 영역에 정보를 저장한다.
		이때 섬의 가장자리의 거리값은 0 으로 저장
	*/
	int island_cnt = 0;
	for (int i = 0; i < N; ++i)
	{
		for (int j = 0; j < N; ++j)
		{
			if (map[i][j] == 1 && cost_map[i][j].island == 0)
			{
				++island_cnt;
				cost_map[i][j].island = island_cnt;
				q.push({i, j});
				bfs_island(map, cost_map, q, island_cnt);
			}
		}
	}

	// map 전체를 순회하며 섬의 가장자리에 있는 위치 인덱스를 큐에 push
	for (int i = 0; i < N; ++i)
	{
		for (int j = 0; j < N; ++j)
		{
			if (cost_map[i][j].cost == BOUNDARY)
			{
				q.push({ i, j });
			}
		}
	}

	// 너비우선 탐색으로 섬으로 부터 떨어진 거리를 cost_map에 저장한다.
	// 최소값 반환
	cout << bfs_bridge(map, cost_map, q);

	return 0;
}

 

 

 

단지번호 붙이기 + 토마토 문제이다.

여러 개의 서로 다른 섬이 있으며, 각각의 섬으로부터 뻗어나가야 한다.

최소 거리를 구해야 한다는 점에서 BFS의 감을 잡고 시작하자.

 

가장 먼저 해야할 것은 1. 각각의 섬을 구분하는 작업이다. 

그리고 나서 각각의 섬으로부터 2. 다른 섬까지 이르는 데 걸리는 최소 거리를 구해야 한다. 

 

그렇다면... 우리에게는 문제를 구하는데 필요한 정보가 2가지 있다는 것을 알 수 있다.

<섬 인덱스, 섬으로부터의 거리>이다. 

 

 

 

1. 각각의 섬을 구분하기

먼저 map 전체를 탐색하며 섬의 영역에 해당하는 지점들을 자료구조에 담아준다.

섬인덱스 따로, 섬으로부터의 거리 따로 자료구조를 2개 만들어도 되고

둘을 struct나 pair로 묶어서 하나의 자료구조로 만들어도 된다.

메모리 효율이 좋게 나온 코드들은 다 정보를 따로따로 2차배열로 만들었더라.

하지만 나는 하나로 묶은 vector를 더 좋아하기 때문에 아래와 같이 코드를 짰다.

// {섬 넘버, 섬으로부터 떨어진 거리}를 저장할 벡터
vector<vector<info>> cost_map(N, vector<info>(N, {0, -1}));
queue<pair<int, int>> q;

/*
    map 전체를 순회하며 섬 영역에 정보를 저장한다.
    이때 섬의 가장자리의 거리값은 0 으로 저장
*/
int island_cnt = 0;
for (int i = 0; i < N; ++i)
{
    for (int j = 0; j < N; ++j)
    {
        if (map[i][j] == 1 && cost_map[i][j].island == 0)
        {
            ++island_cnt;
            cost_map[i][j].island = island_cnt;
            q.push({i, j});
            bfs_island(map, cost_map, q, island_cnt);
        }
    }
}

위 작업은 dfs, bfs 모두 가능하다.

하지만 bfs가 메모리를 좀더 적게 먹는다.

어차피 시간은 둘다 0ms가 나왔기 때문에 bfs로 해주었다.

 

 

bfs_island 함수의 주요 목적은 섬 정보 저장, 그리고 가장자리 여부 체크이다. 

왜냐면...  가장자리부터 바다로 뻗어나가기 때문에!

// 섬에 대한 정보를 너비우선 탐색으로 체크하며 저장한다.
void bfs_island(vector<vector<int>>& map, vector<vector<info>>& cost_map, queue<pair<int, int>> &q, int island_idx)
{
    ...
        // 다음 지점이 map 범위 내이고, 아직 섬 정보를 입력하기 전이면
        if (reachable(map, n_x, n_y) && cost_map[n_x][n_y].island == 0)
        {
            // 다음 지점이 섬일 때
            if (map[n_x][n_y] == 1)
            {
                cost_map[n_x][n_y].island = island_idx;
                q.push({n_x, n_y});
            }
            /*
                다음 지점이 바다일 때 
                = 현재 지점은 섬의 경계선이므로, 현재 지점의 거리값을 0으로 저장 
            */
            else
            {
                cost_map[q_x][q_y].cost = BOUNDARY;
            }
        }
    ...
}

 

 

 

 

2. 다른 섬까지 이르는 데 걸리는 최소 시간 구하기

bfs_island()에서 구한 가장자리 위치값들을 큐에 push해준다.

// map 전체를 순회하며 섬의 가장자리에 있는 위치 인덱스를 큐에 push
for (int i = 0; i < N; ++i)
{
    for (int j = 0; j < N; ++j)
    {
        if (cost_map[i][j].cost == BOUNDARY)
        {
            q.push({ i, j });
        }
    }
}

 

 

그리고 각 섬의 영역을 넓혀가는 식으로 cost_map의 정보를 갱신해나간다. 

{island, cost}에서 뻗어나간 다음 바다는 {island, cost + 1}을 저장한다.

  ex) {2, 1}에서 뻗어나간 바다는 {2, 1 + 1} 을 저장한다.

그리고 다음 바다에 이미 다른 섬의 정보가 저장되어 있다면 

(현재 위치의 cost + 다음 위치의 cost) 가 두 섬이 만나는 거리이다. 

이것의 최소값을 구해주면 된다.

// 섬으로부터의 거리를 너비우선탐색으로 저장하며 섬과 섬 사이의 최소거리를 구한다.
int bfs_bridge(vector<vector<int>>& map,vector<vector<info>> &cost_map, queue<pair<int, int>> &q)
{
    ...
        // 다음 지점에 아직 섬 정보가 저장되지 않았다면 
        if (cost_map[n_x][n_y].island == 0)
        {
            cost_map[n_x][n_y].island = this_island;
            cost_map[n_x][n_y].cost = this_cost + 1;
            q.push({ n_x, n_y });
        }
        // 다음 지점의 섬 정보가 현재 지점과 다른 섬이라면 거리 최소값 갱신
        else if (cost_map[n_x][n_y].island != this_island)
        {
            min_cost = min(this_cost + cost_map[n_x][n_y].cost, min_cost);
        }
    ...
    return min_cost;
}

 

 

 

마지막으로 나에게 매우 도움되었던 반례 2개!

5
0 0 0 0 0
0 0 1 0 0
0 0 0 0 0
0 1 0 1 0
0 0 0 0 0
답 : 1

5
1 0 0 0 1
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
1 1 0 0 1
답 : 2