BOJ - 14466번 소가 길을 건너간 이유 6 (C++)

문제 출처: https://www.acmicpc.net/problem/14466

문제 난이도

Gold 4

문제 접근법

set을 이용해 건초더미를 관리한다.
그리고 cow 쌍을 일일이 맺어보며 dfs로 길 없이 갈 수 있는 위치를 찾는다.

통과 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>

using namespace std;

vector<pair<int, int>> cow;
set<pair<int, int>> arr[101][101];
bool ch[101][101];
int dy[4][2] = { {-1,0},{1,0}, {0,1},{0,-1} };
int N, K, R;

void dfs(int x, int y) {
	if (x < 1 || y < 1 || x > N || y > N) return;
	ch[x][y] = true;
	for (int dir = 0; dir < 4; dir++) {
		int nx = x + dy[dir][0];
		int ny = y + dy[dir][1];
		if (ch[nx][ny] || arr[x][y].count({ nx,ny })) continue;
		dfs(nx, ny);
	}
}

int main() {
	
	int ans = 0;
	cin >> N >> K >> R;
	for (int i = 0; i < R; i++) {
		int a, b, c, d;
		cin >> a >> b >> c >> d;
		arr[a][b].insert( { c,d });
		arr[c][d].insert({ a,b });
	}
	for (int i = 0; i < K; i++) {
		int x, y;
		cin >> x >> y;
		cow.push_back({ x,y });
	}
	for (int i = 0; i < cow.size(); i++) {
		memset(ch, false, sizeof(ch));
		dfs(cow[i].first, cow[i].second);
		for (int j = i + 1; j < cow.size(); j++) {
			if (!ch[cow[j].first][cow[j].second]) ans++;
		}
	}
	cout << ans << "\n";

	return 0;
}

피드백

아래 코드가 틀린 이유
1. map을 사용한 것! key값에 중복이 있을 수 있기 때문이다. -> set 배열 이용
2. 길로 연결된 더미만 체크해서 길 연결 후에 갈 수 있는 좌표는 체크하지 못한다. -> dfs 이용

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>

using namespace std;

vector<pair<int, int>> cow;
map<pair<int, int>, pair<int, int>> arr;

int main() {
	int N, K, R;
	int ans = 0;
	cin >> N >> K >> R;
	for (int i = 0; i < R; i++) {
		int a, b, c, d;
		cin >> a >> b >> c >> d;
		arr[{a, b}] = { c,d };
		arr[{c, d}] = { a,b };
	}
	for (int i = 0; i < K; i++) {
		int x, y;
		cin >> x >> y;
		cow.push_back({ x,y });
	}
	for (int i = 0; i < cow.size()-1; i++) {
		for (int j = i + 1; j < cow.size(); j++) {
			if (arr.find(cow[i]) != arr.end()) {
				pair<int, int> tmp = arr[cow[i]];
				if (tmp.first == cow[j].first && cow[j].second == tmp.second) {
					ans++;
				}
			}
		}
	}
	cout << ans << "\n";

	return 0;
}