Graph B2146

개요

백준 문제 2146번을 풀면서 어려웠던 점과 코드를 정리한다.
소요 시간 : 약 3시간
https://www.acmicpc.net/problem/2146

문제

이 나라는 N×N크기의 이차원 평면상에 존재한다. 이 나라는 여러 섬으로 이루어져 있으며, 섬이란 동서남북으로 육지가 붙어있는 덩어리를 말한다.

색이 있는 부분이 육지이고, 색이 없는 부분이 바다이다. 이 바다에 가장 짧은 다리를 놓아 두 대륙을 연결하고자 한다. 가장 짧은 다리란, 다리가 격자에서 차지하는 칸의 수가 가장 작은 다리를 말한다. 다음 그림에서 두 대륙을 연결하는 다리를 볼 수 있다.

지도가 주어질 때, 가장 짧은 다리 하나를 놓아 두 대륙을 연결하는 방법을 찾으시오.

계획한 풀이법

풀이 방법)

• 번호를 메겨 섬을 체크
• 각 섬마다 BFS를 해가며 가장 짧은 거리의 다리를 찾는다

코드

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;

const int MAX = 100;
const int INF = 987654321;
int mapSize = 0;
int map[MAX][MAX];
bool visit[MAX][MAX];

//왼 오 상 하
int check[4][2] = {{0,-1},{0,1},{-1,0},{1,0}};
//섬 마킹


void DFSMarking(int x, int y, int cnt)
{
        visit[y][x] = true;
        map[y][x] = cnt;
        for (int i = 0; i < 4; i++)
        {
                 int nextY = y + check[i][0];
                 int nextX = x + check[i][1];
                 if (0 <= nextY && nextY < mapSize && 0 <= nextX && nextX < mapSize)
                         if (map[nextY][nextX] && !visit[nextY][nextX])
                                 DFSMarking(nextX, nextY, cnt);
        }
}




void BFSMarking2(int startX,int startY,int numberOfLand)
{
	queue<pair<int,int>> q;
	q.push(make_pair(startX,startY));

	int nextX = 0;
	int nextY = 0;
	visit[startY][startX] = 1;
	map[startY][startX] = numberOfLand;
	
	while(q.size()!=0)
	{
		startX = q.front().first;
		startY = q.front().second;
		q.pop();
		map[startY][startX] = numberOfLand;
		visit[startY][startX] = 1;
		
		for(int i=0;i<4;i++)
		{
			nextY = startY + check[i][0];
			nextX = startX + check[i][1];
			if((nextX >= 0 && nextX <mapSize) && (nextY >= 0 && nextY <mapSize))
			{
				if(!visit[nextY][nextX] && map[nextY][nextX])
				{
					q.push(make_pair(nextX,nextY));
				}
			}
			
		}
	}

}

int BFS(int land)
{
	int count = 0;
	queue<pair<int,int>> q;
	int nextX,nextY,startX,startY;

	for(int i=0;i<mapSize;i++)
	{
		for(int j=0;j<mapSize;j++)
		{
			if(map[i][j] == land)
			{
				q.push(make_pair(j,i));
				//cout << "값 : " << map[i][j] << " land : " << land << "\n";
				//cout << i << " " << j << "pair 추가\n";
				visit[i][j] = 1;
			}
		}
	}	


	int qSize = 0;
	while(q.size() != 0)
	{
		qSize = q.size();
		for(int k=0;k<qSize;k++)
		{

			startX = q.front().first;
			startY = q.front().second;
			q.pop();
			for(int i=0;i<4;i++)
			{
				nextX = startX + check[i][1];
				nextY = startY + check[i][0];
				if((nextX >= 0 && nextX < mapSize) && (nextY >= 0 && nextY < mapSize))
				{
					
					if(map[nextY][nextX] && map[nextY][nextX] != land)
					{
						return count;
					}
					else if(!(map[nextY][nextX]) && !(visit[nextY][nextX]))
					{
						visit[nextY][nextX] = 1;
						q.push(make_pair(nextX,nextY));
					}
				}
			}
		}
		count++;
	} 




}

void init()
{
	cin >> mapSize;
	for(int i=0;i<mapSize;i++)
	{
		for(int j=0;j<mapSize;j++)
		{
			visit[i][j] = false;
			cin >> map[i][j];
		}
	}
}

void solve()
{
	init();
	int curX,curY,numberOfLand = 1,result = INF;

	for(int i=0;i<mapSize;i++)
	{
		for(int j=0;j<mapSize;j++)
		{
			if(!visit[i][j] && map[i][j])
			{
				DFSMarking(j,i,numberOfLand);
				numberOfLand++;
			}

		}
	}


	for(int land=1; land<numberOfLand;land++)
	{
		fill(&visit[0][0], &visit[MAX-1][MAX] ,0);
		result = min(result,BFS(land));
	}
	cout << result;
}

int main()
{
	solve();

}

막혔던 점

1. queue를 사용할때 반복문의 조건으로 q.size()를 사용했었는데
   처음에 의도한 것은 반복문을 시작할 때 q.size()만큼만 돌도록 하는 것이었으나
   q.size()를 사용하면 BFS를 돌면서 q의 크기가 바뀌게 되어서 의도한대로 실행되지 않았다.
   그래서 qSize라는 int 변수로 q.size()값을 저장하고 사용했다.

2. 메모리 초과가 발생했는데 알고보니 섬 번호를 Marking하는 부분을 BFS로 구현했었는데
   그 때문인 것 같다.
   찾아보니 BFS는 큐로 탐색할 노드들을 다 저장하는 특성 상 공간복잡도가 복잡하다.
   DFS와 BFS의 특성에 대해서는 생각을 깊게 안해보았는데, 정리하자면 다음과 같다.

   BFS: 최단경로를 찾는데 유리하다(각 시도마다 여러 경로로 뻗어나가는 모양)

   DFS: 찾아야 하는 노드가 깊다면 유리하다(한번에 깊게 들어가는 모양)

느낀 점

• 이번 문제는 너무 코드 참조를 빠르게 한 것 같다(한시간 정도는 고민을 스스로 해야..)