골드4 - 백준 14466 소가 길을 건너간 이유 6

백준 14466 소가 길을 건너간 이유 6

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

접근방법

목초지의 구역을 나누어 번호를 붙이고, 모든 소의 조합을 구하여 같은 구역의 목초지에 있는지 확인한다. 만약 다른 구역에 있다면 길을 건너야 만날 수 있는 소의 쌍에 추가해주었다.

풀이

각 좌표를 입력받을 때, -1씩 해주어 0,0을 기준으로 바꿔주었다. 그리고 loads에 해당 위치에 있는 다리가 각각 어디로 연결되어 있는지 저장해주고 나중에 BFS를 실행시킬 때, 해당 위치에서 연결되어 있는 목초지는 방문하지 못하도록 해주었다.
반복문을 돌리면서 아직 구역이 정해지지 않은 좌표를 찾았고, 해당 좌표를 기준으로 BFS를 실행하여 같은 구역임을 cur값을 이용해 표시해주었고, BFS가 끝나면 cur값을 1 증가시켜주어 다음 구역을 구분할 수 있게 해주었다.
BFS 내에서는 범위를 벗어난 값, 이미 구역이 정해진 목초지, 다리로 연결되어있는 목초지는 건너뛰도록 해주었고, 일반적으로 갈 수 있는 곳은 같은 구역으로 표시해주었다.
모든 목초지에 대해 구역이 나누어진 이후에는, 소들의 위치를 입력 받았고, 이중 반복문을 통해 모든 소의 조합을 구해서 비교해주었다. 소가 다른 구역에 있다면 result를 1씩 늘려주었다.

코드

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

using namespace std;

int visited[100][100];
vector<pair<int, int>> loads[100][100];
vector<vector<int>> dir = { {0,1}, {0,-1}, {1,0}, {-1,0} };
vector<pair<int, int>> cows;

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

	int N, K, R;
	cin >> N >> K >> R;

	for (int i = 0; i < R; i++)
	{
		int r1, c1, r2, c2;
		cin >> r1 >> c1 >> r2 >> c2;

		r1--;
		c1--;
		r2--;
		c2--;

		loads[r1][c1].push_back({ r2,c2 });
		loads[r2][c2].push_back({ r1,c1 });
	}

	int cur = 1;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			if (visited[i][j] != 0)
				continue;

			queue<pair<int, int>> q;
			q.push({ i,j });
			visited[i][j] = cur;

			// BFS
			while (!q.empty())
			{
				int x = q.front().first;
				int y = q.front().second;
				q.pop();

				for (int i = 0; i < 4; i++)
				{
					int nx = x + dir[i][0];
					int ny = y + dir[i][1];

					if (nx < 0 || nx >= N || ny < 0 || ny >= N)
						continue;

					if (visited[nx][ny] != 0)
						continue;

					// 다리일때
					if (loads[x][y].size() != 0)
					{
						bool flag = false;
						for (int k = 0; k < loads[x][y].size(); k++)
						{
							if (make_pair(nx, ny) == loads[x][y][k])
							{
								flag = true;
								break;
							}
						}

						if (flag)
							continue;
					}

					// 다리가 아닌 일반
					visited[nx][ny] = cur;
					q.push({ nx, ny });
				}
			}

			cur++;
		}
	}
	
	for (int i = 0; i < K; i++)
	{
		int x, y;
		cin >> x >> y;
		x--;
		y--;
		cows.push_back({ x,y });
	}

	int result = 0;

	for (int i = 0; i < K - 1; i++)
	{
		for (int j = i + 1; j < K; j++)
		{
			if (visited[cows[i].first][cows[i].second] == visited[cows[j].first][cows[j].second])
				continue;
			result++;
		}
	}

	cout << result << endl;
}