Why Did the Cow Cross the Road III (Silver)

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

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

개인적으로 해석을 문제를 햇갈리게 하여, 영어로 문제를 읽는걸 추천한다.

(r,c) - (r`,c`) 의 의미는 이 두개의 vertex를 직접 가기 위해서는 길을 건너야 한다는 뜻이다.

즉, 이 두 개 사이에 길이 있다. 

 

이 문제를 풀기 위해서 길이 있으면, 문제에서 건너지 못한다는 조건은 없었으나 이 조건을 하나 더 추가했다.

그렇게 조건을 주고, 임의의 한 소에서 출발하여 BFS를 돌면, 도달하지 못하는 소가 있거나, 없을 수 있는데

이때 도달하지 못하는 소는 반드시 길을 건너야 한다는 것을 생각할 수 있었다.

 

가지 못한다는 표현을 여러가지 다양하게 할 수 있다. 나는 비트마스크를 사용해서 구현해봤다.

모든 소에서 출발하는 BFS를 돌리고 2로 나눠줘서 출력하면 된다.

A소에서 B소를 도달하지 못하면, B소 또한 A소를 도달하지 못하기 때문이다.

좀 더 정교하게 만들수도 있는데, 굳이 그럴필요는 없어 보여서 마무리 지었다.

 

#include <iostream>
#include <algorithm>
#include <iterator>
#include <vector>
#include <string>
#include <string.h>
#include <queue>
#include <stack>
#include <map>
 
#define endl    '\n'
#define FastIO ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
 
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
 
 
int dx[] = { 1,0,-1,0 };
int dy[] = { 0,1,0,-1 };
map<pii, int> st;
 
bool range(int y, int x, int n) {
    return !(y <= 0 || y > n || x <= 0 || x > n);
}
 
int mp[101][101];
bool cow_mp[101][101];
int n, k, r;
bool chk[101][101];
 
int main() {
    FastIO;
 
    for (int dir = 0; dir < 4; dir++)         // 비트마스킹을 하기 위해서 방향도 4개밖에 되지 않는데, 굳이 맵 자료구조를 쓸 필요가 있나 싶겠지만 써봤다.
        st[pii(dy[dir], dx[dir])] = dir;
    
    // 0 : e / 1 : s / 2 : w / 3 : n
    cin >> n >> k >> r;
    for (int i = 0; i < r; i++) {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
 
        int dyy = c - a, dxx = d - b;        // 방향을 구한다.
        mp[a][b] |= (1<<st[pii(dyy, dxx)]);
        dyy *= -1, dxx *= -1;
        mp[c][d] |= (1<<st[pii(dyy, dxx)]);
    }
 
    vector<pii> cows(k);
    for (int i = 0; i < k; i++) {
        cin >> cows[i].first >> cows[i].second;
        cow_mp[cows[i].first][cows[i].second] = true;    // 소를 만났는지 확인하기 위해서 따로 맵을 만들었다.
    }
 
    int ans = 0;
    for (int i = 0; i < k; i++) {
        int cnt = k - 1;                                // bfs를 돌면서 몇명의 소를 마주쳤는지만 알면 된다. 문제가 요구하는건 이보다 더 자세히 요구하지 않는다.
        memset(chk, 0, sizeof(chk));
        queue<pii> q;
        q.push(cows[i]);
        chk[cows[i].first][cows[i].second] = true;
        while (!q.empty()) {
            pii f = q.front();
            q.pop();
            for (int dir = 0; dir < 4; dir++) {
                if (mp[f.first][f.second] & (1 << dir)) continue;        // 비트마스크 표시해논걸 이곳에서 처리하여 걸러낸다.
                int ny = f.first + dy[dir], nx = f.second + dx[dir];
                if (!range(ny, nx, n) || chk[ny][nx]) continue;
                q.push({ ny,nx });
                chk[ny][nx] = true;
                if (cow_mp[ny][nx]) cnt -= 1;            // 소를 마주쳤으므로 하나를 빼준다.
            }
        }
        ans += cnt;                                        // 이곳에 달했을 땐 마주치지 않은 소들의 수만 남는다. 
    }
 
    cout << (ans >> 1);
 
    return 0;
}