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

문제

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

걸린 시간

02 : 37 : 52

풀이

C++

#include <bits/stdc++.h>
#define INF 1e9
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

int N, K, R;
int r, c, rr, cc;
int farm[101][101];
int visited[101][101];
int dy[4] = {1, -1, 0, 0};
int dx[4] = {0, 0, -1, 1};
pair<int, int> cow[100];
map<pair<pair<int, int>, pair<int, int>>, int> way;

int bfs(int src){
    memset(visited, 0, sizeof(visited));
    queue<pair<int, int>> q;
    int sy = cow[src].first;
    int sx = cow[src].second;
    q.push(make_pair(sy, sx));
    visited[sy][sx] = 1;
    while(!q.empty()){
        int cy = q.front().first;
        int cx = q.front().second;
        q.pop();
        for(int i = 0; i < 4; i++){
            int ny = cy+dy[i];
            int nx = cx+dx[i];
            if(1 <= ny && ny <= N && 1 <= nx && nx <= N){
                // 자유 : 0, 길 : 1
                if(way[make_pair(make_pair(cy, cx), make_pair(ny, nx))]) continue;
                if(!visited[ny][nx]){
                    q.push(make_pair(ny, nx));
                    visited[ny][nx] = 1;
                }
            }
        }
    }
    int ret = 0;
    for(int i = src+1; i < K; i++)
        if(!visited[cow[i].first][cow[i].second]) ret++;
    return ret;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> N >> K >> R;
    for(int i = 0; i < R; i++){
        cin >> r >> c >> rr >> cc;
        way[make_pair(make_pair(r, c), make_pair(rr, cc))] = 1;
        way[make_pair(make_pair(rr, cc), make_pair(r, c))] = 1;
    }
    for(int i = 0; i < K; i++){
        cin >> r >> c;
        cow[i] = make_pair(r, c);
    }
    int ans = 0;
    for(int i = 0; i < K; i++)
        ans += bfs(i);
    cout << ans;
    return 0;
}

핵심 아이디어는 소가 길을 사용하지 않고 다른 소의 위치로 이동할 수 있는지를 bfs 탐색을 통해 확인한다.

1번 소 부터 차례로 bfs 를 진행하여 도착하지 못한 다른 소의 위치 개수를 센다.

소의 종류는 같고 순서만 다른 경우, 같은 쌍이므로 조합의 경우수를 구하면 된다.

bfs 가 아닌 다익스트라의 사용, 길을 단방향으로만 저장 하는 바람에 수정과 디버깅에 많은 시간이 걸렸다.