[Algorithm/C++17] 백준 2146 다리 만들기

문제

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

2146번: 다리 만들기

풀이 방법

어느 섬에서 다른 섬에 도달했을 때의 최소 거리를 구해야하는 문제다.

 

N = 100이하이기 때문에 막연하게 생각해봤을 때 O(N^3)이여도 문제가 없을 것 같아 고안해낸 풀이는 다음과 같다.

1. 떨어져 있는 섬끼리 구분하기 위해서, 각 섬에 그래프 탐색을 이용해서 번호를 붙인다.
2. 번호 붙인 섬마다 BFS로 퍼져나가면서 탐색
3. 탐색 중 다른 섬을 만났을 때 거리를 비교해보고 최소일 경우 answer에 저장한다.
4. answer를 출력한다.

아래 코드도 이와 같은 순서이다.

시간제한은 2초이지만 제출했더니 844ms로 나오길래 헉 하고 다른 방법을 찾아보았는데, 찾아본건 아래 고찰에 남겨놓았다.

코드

#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
int dy[] = {-1,0,0,1};
int dx[] = {0,-1,1,0};
int main()
{
    int N;
    scanf("%d", &N);
    vector<vector<int>> v(N, vector<int>(N));
    for(int i=0; i<N; i++)
    {
        for(int j=0; j<N; j++)
        {
            int t;
            scanf("%d", &t);
            v[i][j] = t;
        }
    }
    
    vector<vector<bool>> visited(N, vector<bool>(N, false));
    queue<pair<int, int>> q;
    // 섬을 구별하기 위해 섬마다 번호를 붙인다.
    int islandNum = 1;
    for(int i=0; i<N; i++)
    {
        for(int j=0; j<N; j++)
        {
            if(v[i][j] && !visited[i][j])
            {
            	v[i][j] = islandNum;
                q.push({i,j});
                visited[i][j] = true;
                while(!q.empty())
                {
                    int y = q.front().first;
                    int x = q.front().second;
                    q.pop();
                    for(int k=0; k<4; k++)
                    {
                        int ny = y + dy[k];
                        int nx = x + dx[k];
                        if(ny < 0 || ny >= N || nx < 0 || nx >= N)
                            continue;
                        if(!v[ny][nx] || visited[ny][nx])
                            continue;
                        q.push({ny, nx});
                        visited[ny][nx] = true;
                        v[ny][nx] = islandNum;
                    }
                }
                islandNum++;
            }
        }
    }
    
    // 각 섬의 다리 길이 계산
    int answer = 0x7fffffff;
    for(int i=1; i<islandNum; i++)
    {
    	queue<pair<int, int>> q2;
    	fill(visited.begin(), visited.end(), vector<bool>(N, false));
    	// 현재 섬 좌표들을 큐에 모두 넣는다.
    	for(int j=0; j<N; j++)
    	{
    		for(int k=0; k<N; k++)
    		{
    			if(v[j][k] == i) 
    			{
    				visited[j][k] = true;
    				q2.push({j,k});
    			}
    		}
    	}
    	// 한 칸씩 탐색하면서 다른 섬을 만나기까지 얼마나 걸리는지 계산한다.
    	int dist = 0;
    	while(!q2.empty())
    	{
    		bool found = false;
    		int qsize = q2.size();
    		for(int j=0; j<qsize; j++)
    		{
    			if(found) break;
    			int y = q2.front().first;
    			int x = q2.front().second;
    			q2.pop();
    			for(int k=0; k<4; k++)
    			{
    				int ny = y + dy[k];
    				int nx = x + dx[k];
                    if(ny < 0 || ny >= N || nx < 0 || nx >= N)
                        continue;
                    if(visited[ny][nx])
                        continue;
                    
                    visited[ny][nx] = true;
                    q2.push({ny,nx});
                    // 다른 섬을 만나면 다리 길이를 계산한다.
                    if(v[ny][nx] != i && v[ny][nx] != 0)
                    {
                        answer = min(dist, answer);
                        found = true;
                        break;
                    }
    			}
    		}
            dist++;
    	}
    	
    }
    printf("%d", answer);
    return 0;
}

고찰

내 생각과 달리 위의 풀이는 O(N^3)이 아니라 O(N^4)가 걸리는 풀이였다. 

BaaaaaaaarkingDog 님께서 작성하신 코드를 참고했다. BFS 관련된 시간 복잡도 생각하는 방법도 여기 나와있다.

 

모든 섬에서 동시에 BFS를 돌려 섬의 영역을 확장하다가 겹쳐지는 순간을 찾는 방식이 핵심이다.

혼자 생각하기엔 꽤 어렵다. 코드를 보고 개선해서 제출하니 0ms가 걸린다.

위 링크의 코드와 비슷하긴 하지만 그래도 올려본다.

개선  코드

#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
int dy[] = {-1,0,0,1};
int dx[] = {0,-1,1,0};
int main()
{
    int N;
    scanf("%d", &N);
    vector<vector<int>> v(N, vector<int>(N));
    for(int i=0; i<N; i++)
    {
        for(int j=0; j<N; j++)
        {
            int t;
            scanf("%d", &t);
            v[i][j] = t;
        }
    }
    
    vector<vector<bool>> visited(N, vector<bool>(N, false));
    queue<pair<int, int>> q;
    // 섬을 구별하기 위해 섬마다 번호를 붙인다.
    int islandNum = 1;
    for(int i=0; i<N; i++)
    {
        for(int j=0; j<N; j++)
        {
            if(v[i][j] && !visited[i][j])
            {
            	v[i][j] = islandNum;
                q.push({i,j});
                visited[i][j] = true;
                while(!q.empty())
                {
                    int y = q.front().first;
                    int x = q.front().second;
                    q.pop();
                    for(int k=0; k<4; k++)
                    {
                        int ny = y + dy[k];
                        int nx = x + dx[k];
                        if(ny < 0 || ny >= N || nx < 0 || nx >= N)
                            continue;
                        if(!v[ny][nx] || visited[ny][nx])
                            continue;
                        q.push({ny, nx});
                        visited[ny][nx] = true;
                        v[ny][nx] = islandNum;
                    }
                }
                islandNum++;
            }
        }
    }
    
    // 각 섬의 다리 길이 계산
    int answer = 0x7fffffff;
    //
    // 여기서 부터 수정되었음
    //
    vector<vector<int>> dist(N, vector<int>(N, -1));
    for(int i=0; i<N; i++)
    {
        for(int j=0; j<N; j++)
        {
            if(v[i][j] != 0)
            {
                q.push({i,j});
                dist[i][j] = 0;
            }
        }
    }
    
    while(!q.empty())
    {
        int qsize = q.size();
        for(int i=0; i<qsize; i++)
        {
            int y = q.front().first;
            int x = q.front().second;
            q.pop();
            for(int j=0; j<4; j++)
            {
                int ny = y+dy[j];
                int nx = x+dx[j];
                if(ny < 0 || ny >= N || nx < 0 || ny >= N) 
                    continue;
                if(v[ny][nx] == v[y][x])
                    continue;
                // 인접한 곳이 다른 섬일때
                // 섬으로부터 떨어진 (ny,nx) 거리 +  다른 섬으로부터 떨어진 (y,x) 거리
                // = 다리의 길이
                if(v[ny][nx] != 0) 
                {
                    answer = min(answer, dist[ny][nx] + dist[y][x]);
                }
                else
                {
                    // 섬의 영역 확장, 거리 갱신
                    v[ny][nx] = v[y][x];
                    dist[ny][nx] = dist[y][x]+1;
                    q.push({ny,nx});
                }
            }
        }
    }
    printf("%d", answer);
    return 0;
}