[C++]백준 14466번 : 소가 길을 건너간 이유

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

14466번: 소가 길을 건너간 이유 6

 

1. 접근 : 단순 BFS 원리만 사용해서 성공은 했지만 메모리와 싱행시간이 너무 컸다.

한 마리씩 BFS 돌면서 못 만난 마릿수를 최종결과 값에 더해주고 해당 기준 소는 다음 경우에서 제외

(즉 i번째로 기준 잡은 소는 (K-i)만큼의 소와의 경우를 check, 마지막 소는 check 안해도 된다.)

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

using namespace std;

int N, K, R, r1, r2, c1, c2;
bool block[101][101][101][101] = { false, }; // 울타리
bool cow[101][101] = { false, }; // 소 위치
queue<pair<int, int>> cq;
int cowCnt = 0;

int dx[4] = { -1, 1, 0, 0 };
int dy[4] = { 0, 0, -1, 1 };

int ans = 0;

int main(){

	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	cin >> N >> K >> R;

	for (int i = 0; i < R; i++){
		cin >> r1 >> c1 >> r2 >> c2;
		block[r1][c1][r2][c2] = true;
		block[r2][c2][r1][c1] = true;
	}

	for (int i = 0; i < K; i++){
		cin >> r1 >> c1;
		cow[r1][c1] = true;
		cowCnt++;
		cq.push({ r1, c1 });
	}

	while (cq.size() > 1){
		int cCowCnt = --cowCnt; // 못 만난 마릿수

		int r = cq.front().first, c = cq.front().second;
		cow[r][c] = false; 
		cq.pop();

		bool chk[101][101] = { false, };

		queue<pair<int, int>> q;
		q.push({ r, c });
		chk[r][c] = true;

		while (!q.empty()){
			int cr = q.front().first, cc = q.front().second;
			q.pop();
		
			for (int i = 0; i < 4; i++){
				int nr = cr + dy[i], nc = cc + dx[i];

				if (nr < 1 || nr > N || nc < 1 || nc > N)
					continue;
				if (chk[nr][nc] || block[cr][cc][nr][nc])
					continue;

				if (cow[nr][nc]){ // 만났다면
					cCowCnt--; // 못만난 마릿수--
				}
				q.push({ nr, nc });
				chk[nr][nc] = true;
			}
		}

		ans += cCowCnt;
	}

	cout << ans;

	return 0;
}

 

2. set을 이용한 풀이

각각의 소를 기준으로 전체 맵 도달 cost를 확인한다. 울타리를 넘는 경우 cost>0

그리고 cost>0인 자리에 다른 소가 있다면 set에 쌍을 저장한다.

그러면 중복되지 않은 쌍이 set에 저장될테니 set.size()를 출력해주면 된다.

메모리도 그대로고 시간은 오히려 5배 늘었다

#include <iostream>
#include <vector>
#include <queue>
#include <set>
#include <climits>

using namespace std;

struct inf{
	int y, x, cost;
};

struct comp{
	bool operator()(inf a, inf b){
		return a.cost > b.cost;
	}
};

int N, K, R, r1, r2, c1, c2;
bool block[101][101][101][101] = { false, }; // 울타리
vector<pair<int, int>> v;
priority_queue<inf, vector<inf>, comp> pq;
inf tmp;

int dx[4] = { -1, 1, 0, 0 };
int dy[4] = { 0, 0, -1, 1 };

int d[101][101]; // {dis, cost}

set<pair<int, int>> ans;

int main(){

	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	cin >> N >> K >> R;

	for (int i = 0; i < R; i++){
		cin >> r1 >> c1 >> r2 >> c2;
		block[r1][c1][r2][c2] = true;
		block[r2][c2][r1][c1] = true;
	}

	for (int i = 0; i < K; i++){
		cin >> r1 >> c1;
		v.push_back({ r1, c1 });
	}

	for (int i = 0; i < K; i++){

		// 초기화
		for (int j = 1; j <= N; j++)
			for (int k = 1; k <= N; k++)
				d[j][k] = INT_MAX;

		// 기준 소
		tmp = { v[i].first, v[i].second, 0 };
		pq.push(tmp);

		while (!pq.empty()){
			int r = pq.top().y, c = pq.top().x, cost = pq.top().cost;
			pq.pop();

			for (int j = 0; j < 4; j++){
				int nr = r + dy[j], nc = c + dx[j], ncost = cost;

				if (nr<1 || nr>N || nc<1 || nc>N)
					continue;
				if (block[r][c][nr][nc]) // 울타리를 넘어간 경우
					ncost++;
								
				if (d[nr][nc] <= ncost)
					continue;
				else{
					d[nr][nc] = ncost;
					tmp = { nr, nc, ncost };
					pq.push(tmp);
				}	
			}
		}

		for (int j = 0; j < K; j++){
			if (i == j) continue;
			if (d[v[j].first][v[j].second]>0)
				ans.insert({ min(i, j), max(i, j) });
		}
	}

	cout << ans.size();

	return 0;
}

 

3. 유니온파인드

길을 건너지 않고 갈 수 있는 맵을 유니온시킨 뒤, 같은 parent 값을 갖지 않은 소의 위치 쌍 개수를 세어준다.

메모리는 1/100배, 시간은 10배 줄일 수 있었다.

 

포인트는

1. 인접한 농장의 울타리 여부를 3차원 배열로 표현

2. N*N맵의 유니온 표현을 1차원배열의 parent로 표현 : N<=100이기 때문에 최대 수용은 10100

3. parent 배열의 size 설정 및 표현식(y*N + x) : 표현식은 1<= y,x <=N 이기 때문에 가능

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

using namespace std;

int N, K, R, r1, r2, c1, c2, dy, dx;
bool block[101][101][4]; // 상, 우, 하, 좌 울타리 여부
pair<int, int> dir[4] = { { -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 } }; // 상, 우, 하, 좌
pair<int, int> cow[10001];
int parent[10101];

int ans = 0;

int find(int n){
	if (parent[n] == n)
		return n;
	
	return parent[n] = find(parent[n]);
}

void merge(int n1, int n2){
	int x = find(n1);
	int y = find(n2);

	if (x != y)
		parent[max(x, y)] = min(x, y);
}


int main(){

	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

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

		if (r1 == r2){
			if (c1 > c2) swap(c1, c2); // c1 < c2
			block[r1][c1][1] = block[r2][c2][3] = true;
		}
		else if (c1 == c2){
			if (r1 > r2) swap(r1, r2); // r1 < r2
			block[r1][c1][2] = block[r2][c2][0] = true;
		}
	}

	for (int i = 1; i <= K; i++){
		cin >> r1 >> c1;
		cow[i] = { r1, c1 };
	}

	// 초기화
	for (int i = 1; i <= 10100; i++)
		parent[i] = i;

	for (int y = 1; y <= N; y++){
		for (int x = 1; x <= N; x++){
			for (int k = 0; k < 4; k++){
				int ny = y + dir[k].first, nx = x + dir[k].second;

				if (ny<1 || ny>N || nx<1 || nx>N || block[y][x][k]) continue;

				merge(find(y*N + x), find(ny*N + nx)); // 1 <= i, j <= N -> (i*N + j) is never dup
			}
		}
	}

	for (int i = 1; i <= K; i++)
		for (int j = i + 1; j <= K; j++)
			if (find(cow[i].first*N + cow[i].second) != find(cow[j].first*N + cow[j].second)) ans++;

	cout << ans;

	return 0;
}

 

여러 방법으로 풀어볼 수 있는 아주 좋은 문제 같다.