Graph B4963

개요

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

문제
정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오.

한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형이다.

두 정사각형이 같은 섬에 있으려면, 한 정사각형에서 다른 정사각형으로 걸어서 갈 수 있는 경로가 있어야 한다. 지도는 바다로 둘러싸여 있으며, 지도 밖으로 나갈 수 없다.

입력
입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다.

둘째 줄부터 h개 줄에는 지도가 주어진다. 1은 땅, 0은 바다이다.

입력의 마지막 줄에는 0이 두 개 주어진다.

출력
각 테스트 케이스에 대해서, 섬의 개수를 출력한다.

예제 입력 1 
1 1
0
2 2
0 1
1 0
3 2
1 1 1
1 1 1
5 4
1 0 1 0 0
1 0 0 0 0
1 0 1 0 1
1 0 0 1 0
5 4
1 1 1 0 1
1 0 1 0 1
1 0 1 0 1
1 0 1 1 1
5 5
1 0 1 0 1
0 0 0 0 0
1 0 1 0 1
0 0 0 0 0
1 0 1 0 1
0 0

예제 출력 1
0
1
1
3
1
9  

계획한 풀이법

• 그래프 연결(연결되지 않으면 자기자신만 연결)
• DFS로 개수 세기

그래프 연결

이번에는 map이라는 2차원 배열과 벡터 2차원 배열을 사용했다.
우선 입력 자체는 map에 우선 입력 후 벡터 2차원 배열(그래프 연결)에 edge들을 연결하는 식으로 구현했다.
지금 생각해보니 map이 없어도 입력받은 값들의 이전 값들만 이용하여 연결 할 수 있을 것 같다. (왼쪽 배열 값과 위쪽 배열 값, 대각선 배열 값)

생각한 팁

그래프를 연결할 때, 다른 edge와 연결이 되더라도 자신이 1이라면 자기 자신과의 사이클을 형성하는 것이 편하다.
다른 edge와 연결이 안 된 경우와 자기 자신의 사이클을 형성하는 것을 분리해 버리면 예외처리가 너무 복잡해지는 것 같았다.

오래걸렸던 이유

문제 자체는 해결 방법을 빠르게 생각했다.
실제로 크게 어렵지 않은 문제이기도 하고 대부분 현한 그대로가 정답일 수 있다고 생각한다.
우선 결론부터 짓으면 c++에 아직 익숙치 않아 속도가 나지 않는다고 생각한다.
이것은 구현력이 부족하다고 할 수 있겠다.
디버깅을 하면서 다음과 같은 문제가 있었다.

• 벡터를 초기화할 때 이전 테스트 케이스의 벡터 크기가 남아있음.(초기화 문제)
• 가로와 세로 크기를 입력 받은 뒤 둘을 서로 바꿔 생각함
  속도 향상을 위해서 한번에 꼼꼼하게 코딩하도록 하고 익숙치 않은 함수들에 익숙해 지려고 노력해야 겠다.

코드

#include <iostream>
#include <vector>
#include <stack>
using namespace std;
const int MAX = 2500;

vector<vector<int>> graph;
int map[MAX][MAX];
int visit[MAX];

//전역변수 써서 코드 간결하게 짜보기


void init(int row,int cal)
{	
    for(int i=0;i < graph.size();i++)
	{
		graph[i].clear();
	}
	graph.clear();
	int maxIdx = row * cal;
	for(int i = 0;i<row;i++)
	{
		for(int j= 0;j<cal;j++)
		{
			cin >> map[i][j];
		}
	}
	for(int i=0;i<maxIdx;i++)
	{
		vector<int> tmp;
		graph.push_back(tmp);
	}
}

void connectEdge(int v,int e)
{
	//////cout << "V와 E 연결\n";
	//////cout << v << " " << e <<"\n";
	graph[v].push_back(e);
	graph[e].push_back(v);
}

int DFS(int startV)
{
	int onesCheck = 0;
	stack <int> s;
	s.push(startV);
	int curV = 0;
	//cout << "시작 정점 : " << startV << "\n";
	while(s.size()!= 0)
	{
		curV = s.top();
		//cout << "V : " << curV << "\n";
		s.pop();
		
		visit[curV] = true;
		//cout << graph[curV].size() << "<- 크기\n";
		for(int i=0;i<graph[curV].size();i++)
		{
			if(!visit[graph[curV][i]])
			{
				s.push(graph[curV][i]);
			}			
			onesCheck = 1;
		}



	}	
	
	if(onesCheck)
	{
		return 1;
	}

	return 0;



}



void edgeConnect(int width,int height)
{
	int idx = 0;
	int isLeftLand = 0;
	int isCurLand = 0;
	int isUpLand = 0;
	int isLeftDiagonalLand = 0;
	int isRightDiagonalLand = 0;


	for(int row = 0; row < height; row++)
	{
		for(int cal = 0;cal < width; cal++,idx++)
		{
			isCurLand = map[row][cal];
			if(isCurLand)
			{
				//cout << idx << "번째 연결 시도\n";
				int isConnectedOnce = 0;
				if(cal-1 >= 0)
				{
					//왼쪽 연결
					isLeftLand = map[row][cal-1];
					if(isLeftLand)
					{
						//cout << "왼쪽 연결\n";
						connectEdge(idx,idx-1);
						isConnectedOnce = 1;
					}
				}
				if(row != 0)
				{
					//위 연결
					isUpLand = map[row-1][cal];
					if(isUpLand)
					{
						//cout << "위 연결\n";

						connectEdge(idx,idx-width);
						isConnectedOnce = 1;

					}

					//왼쪽 대각선 연결
					if(cal != 0)
					{
						isLeftDiagonalLand = map[row-1][cal-1];
						if(isLeftDiagonalLand)
						{
							//cout << "왼쪽 위 대각선 연결\n";

							connectEdge(idx,idx-1-width);
							isConnectedOnce = 1;

						}
					}

					//오른 대각선 연결
					if(cal+1 != width)
					{
						isRightDiagonalLand = map[row-1][cal+1];
						if(isRightDiagonalLand)
						{
							//cout << "오른 위 대각선 연결\n";
							connectEdge(idx,idx+1-width);
							isConnectedOnce = 1;

						}
					}
				}

				if(!isConnectedOnce)
				{
					//cout << "자기자신 연결\n";
					connectEdge(idx,idx);
				}

			}
		}
	}
}

void printAll(int height,int width)
{
	//cout << "프린트 시작 : \n";
	for(int row = 0;row<height;row++)
	{
		for(int cal = 0; cal<width;cal++)
		{
			//cout << map[row][cal] << " ";
		}
		//cout << "\n";
	}
	//cout << "프린트 종료\n";
}

void solve()
{
	int width = -1;
	int height = -1;
	int maxIdx = 0;
	int landCount = 0;
	int count = 0;
	while(1)
	{
		//cout << ++count << "번째 테스트케이스\n";
		landCount = 0;
		cin >> width >> height;
		//cout << width << " " << height << "\n";
		maxIdx = width * height;
		if(width == 0 && height == 0)
		{
			break;
		}
		
		fill_n(visit,MAX,0);
		fill(&map[0][0],&map[MAX-1][MAX],0);
		//벡터 해제 필요
		init(height,width);

		if(width == 1 && height == 1)
		{
			cout << map[0][0] << "\n";
			continue;
		}
		
		edgeConnect(width,height);
		for(int i = 0;i<maxIdx;i++)
		{
			if(!visit[i])
			{
				int result = 0;
				//cout << i << "번째 DFS 시작\n";
				result = DFS(i);
				if(result)
				{
					//cout << i << "번째 DFS의 탐색 성공\n";
				}
				landCount += result;

			}
		}
		cout << landCount << "\n";
	}



}

int main()
{
	solve();
}

익숙해져야 할 함수

• 2차원 벡터 초기화

   //아래의 코드로 구현해서 테스트 케이스마다 벡터가 제대로 초기화 되지 않음
//MAX x MAX의 2차원 벡터 생성
vector<vector<int>> graph(MAX, vector<int>(MAX));
//앞의 두 인자는 어디부터 어디까지, 세번째 인자는 넣을 값
//begin부터 end까지 각 row에 MAX만큼의 각 vector<int>를 0으로 초기화한다 

fill(graph.begin(), graph.end(), vector<int>(MAX, 0));


//테스트 케이스마다 아래의 코드로 초기화 해주어야 했음.
for(int i=0;i <graph.size();i++)
{
	graph[i].clear();
}
graph.clear();

``