[백준] 14466-소가 길을 건너간 이유(C++)

문제링크: https://www.acmicpc.net/problem/14466

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

 

문제를 이해하는데 오래 걸렸습니다.

즉 N x N 구역의 좌표들에 소가 분포해있습니다.

 

문제에서 주어지는 길을 피해서 이동하여 소들은 만날 수가 있겠죠.

하지만 특정한 소들은 꼭 길을 포함해서 이동할때에만 만날 수가 있습니다.

그 소의 개수를 출력하라는 문제입니다.

 

문제에서 주어진 예시에서는 

A(3,3), B(2,2), C(2,3)  이렇게 3마리 소가 있습니다. 

B(2,2)와 C(2,3)는 2,2 -> 1,2 -> 1,3 -> 2,3 경로로 움직여서 길을 포함하지 않더라도 만날 수 있습니다.

하지만 A,B와 A,C는 길을 포함하지 않고 만날 수 가 없습니다. 

그래서 총 2쌍이라는 겁니다.

 

 

접근방식

 

1. 일반적인 bfs로 구현해보자

 

문제풀이 

 

1. 길을 마킹할 배열 arr[101][101][4] 를 생성 북,동,남,서 순으로 이동이 불가한 위치를 표시할 용도

2. bfs를 통해 소 기준으로 이동이 불가한 소들을 도출

3. bfs를 반복해줄때, 이전 소들은 확인할 필요없이 자신보다 인덱스가 높은 소들만 확인해주면서 넘어가야 중복이 안생김

 

 

코드를 직접 확인하는게 더 빠를 것 같음

#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
using namespace std;

int n, k, R;
int arr[101][101][4] = { 0, }; // 4방향에 대해서 길이 있을 수 있으니.. 북 동 남 서 순으로 저장할거
bool visited[101][101];
int y_ar[4] = { -1,0,1,0 };
int x_ar[4] = { 0,1,0,-1 };

vector <pair<int, int>> cow;
int result = 0;
void bfs(int sy, int sx) {

	queue <pair<int, int >> que;
	que.push(make_pair(sy, sx));
	visited[sy][sx] = 1;

	while (!que.empty()) {
		int cy = que.front().first;
		int cx = que.front().second;
		que.pop();

		for (int i = 0; i < 4; i++) {
			if (arr[cy][cx][i] == 1) continue; //도로가 있는건 탐색 안해줄거야
			int ny = cy + y_ar[i];
			int nx = cx + x_ar[i];

			if (ny <1 || ny > n || nx < 1 || nx > n || visited[ny][nx] == 1)
				continue;
			que.push(make_pair(ny, nx));
			visited[ny][nx] = 1;
		}



	}


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

	cin >> n >> k >> R;

	int r, c, rr, cc;
	for (int i = 0; i < R; i++) {
		cin >> r >> c >> rr >> cc;
		for (int j = 0; j < 4; j++) {
			int nr = r + y_ar[j];
			int nc = c + x_ar[j];
			if (nr == rr && nc == cc) {
				arr[r][c][j] = 1; // 다리 생성
				arr[rr][cc][(j + 2)%4] = 1;
			}
		}
	}

	for (int i = 0; i < k; i++) {
		cin >> r >> c;
		cow.push_back(make_pair(r, c)); 
	}

	for (int i = 0; i < k; i++) {
		memset(visited, 0, sizeof(visited));
		bfs(cow[i].first, cow[i].second);

		for (int j = i + 1; j < k; j++) {
			if (visited[cow[j].first][cow[j].second] == 0)
				result++;
		}
	}


	cout << result << endl;
	return 0;
}