[백준 문제 C++] 3197 백조의 호수

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

3197번: 백조의 호수

 

물(.) 옆에 있는 빙판(X)은 하루가 지날 때 마다 사라집니다.

백조(L) 두 마리가 며칠 뒤에 만날 수 있는가를 탐색하는 문제입니다.

 

제가 한 풀이는 이렇습니다. 우선 분리 집합을 통해 그룹화 시켜주었습니다.

( 분리 집합(Disjoint Set) 을 잘 모르시는 분은 나중에 다시 글을 올려 링크해 두겠습니다. )

 

1. 모든 지형을 탐색합니다. 물이나 백조인 곳을 기점으로 번호를 매겨 DFS 탐색을 해줍니다.

2.  .이라면 계속 탐색하고, X를 만나면 탐색을 중지하고 큐에 넣어줍니다.

 

 

3. 백조 두 마리가 처음부터 같은 그룹에 있을 수 있습니다. 이를 확인하여 처리해 줍니다.

 

4.

 4-1. X 위치에서 주변을 탐색하고 분리 집합 (parent)을 사용하여 같은 그룹으로 만들어 줍니다.

bird[1] = 3 에서 1로 변경되었습니다.

 4-2. bird[0] 과 bird[1] 이 같으면 백조는 서로 만나게 된 상태입니다.

      만났다면 day를 출력

      만나지 못했다면 day를 1 증가 시키고 4-3으로 갑니다.

 

 4-3. 다시 주변 X를 queue에 넣어주며 4를 반복합니다.

 

 

 

 

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

using namespace std;

queue<pair<int, int>> q;
vector<int> bird;
vector<int> parent;

char input[1500][1501];
int visited[1500][1500];
int dir[4][2] = 
{
	{1, 0},
	{0, 1},
	{-1, 0},
	{0, -1}
};

void DFS(int startRow, int startCol, int r, int c, int group)
{
	if (input[startRow][startCol] == 'L')
	{
		bird.push_back(group); //새가 어느 그룹에 속해있는지 저장해둡니다.
	}

	for (int i = 0; i < 4; ++i)
	{
		int nextRow = startRow + dir[i][0];
		int nextCol = startCol + dir[i][1];

		if (nextRow < 0 || r <= nextRow ||
			nextCol < 0 || c <= nextCol ||
			visited[nextRow][nextCol] > 0)
		{
			continue;
		}
		
		visited[nextRow][nextCol] = group;

		if (input[nextRow][nextCol] == 'X')
		{
			q.push(make_pair(nextRow, nextCol));
		}
		else
		{
			DFS(nextRow, nextCol, r, c, group);
		}
	}
}

int GetParent(int p)
{
	if (parent[p] == p)
	{
		return p;
	}

	return parent[p] = GetParent(parent[p]);
}

int SetParent(int from, int to)
{
	return parent[from] = parent[to];
}

//테스트 출력용
void PrintState(int r, int c, int day)
{
	cout << endl << "day : " << day << endl;

	for (int i = 0; i < r; ++i)
	{
		for (int j = 0; j < c; ++j)
		{
			cout << GetParent(visited[i][j]) << "";
		}
		cout << endl;
	}

	cout << "parent : " << endl;

	for (int i = 1; i < parent.size(); ++i)
	{
		cout << "[" << i << "] " << parent[i] << " ";
	}

	cout << endl;
}

int main()
{
	int r, c;
	int day = 1;
	int groupId = 1;
	cin >> r >> c;

	parent.push_back(0);
	for (int i = 0; i < r; ++i)
	{
		cin >> input[i];
	}

	for (int i = 0; i < r; ++i)
	{
		for (int j = 0; j < c; ++j)
		{
			if (visited[i][j] > 0)
			{
				continue;
			}

			if (input[i][j] == '.' || input[i][j] == 'L') //탐색 및 그룹화
			{
				visited[i][j] = groupId;
				DFS(i, j, r, c, groupId);
				parent.push_back(groupId);
				groupId++;
			}
		}
	}

	if (GetParent(bird[0]) == GetParent(bird[1])) //이미 만나 있는 상태
	{
		cout << 0 << endl;
		return 0;
	}

	while (!q.empty())
	{
		int size = q.size();

		//4-1
		for (int i = 0; i < size; ++i)
		{
			q.push(q.front());

			int row = q.front().first;
			int col = q.front().second;
			int group = GetParent(visited[row][col]);
			q.pop();

			for (int j = 0; j < 4; ++j)
			{
				int nextRow = row + dir[j][0];
				int nextCol = col + dir[j][1];

				if (nextRow < 0 || r <= nextRow ||
					nextCol < 0 || c <= nextCol || 
					visited[nextRow][nextCol] == 0)
				{
					continue;
				}
				int from = GetParent(visited[nextRow][nextCol]);

				SetParent(from, group);
			}
		}

		//4-2
		PrintState(r, c, day);
		if (GetParent(bird[0]) == GetParent(bird[1]))
		{
			break;
		}
		
		//4-3
		day++;
		for (int i = 0; i < size; ++i)
		{
			int row = q.front().first;
			int col = q.front().second;
			int group = visited[row][col];
			q.pop();

			for (int j = 0; j < 4; ++j)
			{
				int nextRow = row + dir[j][0];
				int nextCol = col + dir[j][1];

				if (nextRow < 0 || r <= nextRow ||
					nextCol < 0 || c <= nextCol ||
					visited[nextRow][nextCol] > 0)
				{
					continue;
				}

				visited[nextRow][nextCol] = group;
				q.push(make_pair(nextRow, nextCol));
			}
		}
	}

	cout << day << endl;
}