[BOJ/백준][Gold4] 14466 : 소가 길을 건너간 이유 6 (C++)

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

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

 

 

[난이도] Gold4
[유형] BFS

[풀이]
K마리의 소로 만들 수 있는 모든 쌍에 대해
길을 건너지 않고 서로 방문할 수 있는 쌍의 개수를 찾으면 됩니다.
길을 저장할 때 adj[101][101][101][101] 형식의 배열로 저장하는 것은 배열의 메모리 문제로
불가능 하므로 (r1,c1)<->(r2,c2) 의 길은 set<int> adj[20001] 형태의 set을 선언하여
adj[r1*N+c1].insert(r2*N+c2) 와 같이 set을 이용하여 저장해줍니다.

그 뒤, 모든 쌍의 소 간에 BFS를 통해 위에 미리 저장해놓은 길을 이용하지 않고 방문할 수 있는지를
구해주어, 정답에 방문할 수 있으면 0, 방문할 수 없으면 1을 더해주면
길을 건너지 않으면 만날 수 없는 소의 쌍을 구할 수 있습니다.

 

 

#include <cstdio>
#include <queue>
#include <set>
#include <vector>
#include <cstring>
using namespace std;
int N,K,R;
bool visit[101][101];
int dy[4]={-1,1,0,0};
int dx[4]={0,0,1,-1};
set<int> adj[20001];
vector<pair<int,int>> v;
int sol(int s,int e){
    memset(visit,0,sizeof(visit));
    queue<pair<int,int>> q;
    q.push({v[s].first,v[s].second});
    visit[v[s].first][v[s].second]=1;
    while(!q.empty()){
        auto [y,x] = q.front(); q.pop();
        if(y==v[e].first && x==v[e].second) return 0;
        for(int i=0;i<4;i++){
            int ny=y+dy[i],nx=x+dx[i];
            if(ny<1||nx<1||ny>N||nx>N||visit[ny][nx]||adj[y*N+x].find(ny*N+nx) != adj[y*N+x].end()) continue;
            q.push({ny,nx});
            visit[ny][nx]=1;
        }
    }
    return 1;
}
int main(){
    scanf("%d%d%d",&N,&K,&R);
    while(R--){
        int r1,c1,r2,c2;
        scanf("%d%d%d%d",&r1,&c1,&r2,&c2);
        adj[r1*N+c1].insert(r2*N+c2);
        adj[r2*N+c2].insert(r1*N+c1);
    }
    while(K--){
        int y,x;
        scanf("%d%d",&y,&x);
        v.push_back({y,x});
    }
    int ans=0;
    for(int i=0;i<v.size()-1;i++)
        for(int j=i+1;j<v.size();j++) ans+=sol(i,j);
    printf("%d",ans);
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/14466.cpp