[백준] 14466 소가 길을 건너간 이유6

문제 : 백준

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

흔한 BFS문제이나 생각보다 시간 초과가 계속 발생해서 고전한 문제이다.

효율적인 문제 접근을 위해서 방문 여부 처리와 소들간의 만남 여부 처리가 중요하다. 

 

점차 발전해나가면서 시도한 결과는 아래와 같다.

- BFS를 소를 일대일 대응시키고 연결되면 BFS 탐색 종료한다.

- 일대일 대응은 비효율적. 소들간에 경로가 겹치는 경우에는 중복적인 작업이 많이 이루어진다. 그래서 일대다 대응으로 소들간의 연결 가능성을 탐색한다. 그리고 매 탐색이 끝난 뒤에 2차원 map을 순회하면서 연결된 소와 연결되지 못한 소를 파악한다.

- 매번 2차원 배열을 탐색하는 것이 비효율적. 그래서 아예 소들간의 인덱스를 기준으로 만남의 여부를 저장하는 별도의 배열 생성

(int meet[][])

- 1번째 소 ~ k번째 소까지 인덱스를 정하고 이를 2차원 map에 소의 인덱스로 소의 위치를 표시한다. 이후 BFS 탐색 중 a번째 소와 b번째 소의 연결관계를 meet[a][b] = 0 or 1로 처리한다.

/**
 * 어떻게 해야 효율적으로 소들간의 연결성을 확인할 수 있는가
 * 매번 소들마다 확인하는 것이 아니라, a번째 소와 b번째 소의 연결관계를 meet[a][b]에 저장 (if a<b)
 */
#include <iostream>
#include <queue>
using namespace std;
// 2차원 농장 표현
int farm[101][101] = {0};
// 다리 안 건너고도 만날 수 있는 소 확인(0:못만남/1:만남)
int meet[101][101] = {0};
int dr[4] = {-1, 0, 1, 0};
int dc[4] = {0, 1, 0, -1};
vector<pair<int,int>> cows;
int bridge[101][101][4] = {0};
int n, k, r;
int ans = 0;
bool inside(int r, int c);
// idx 번째 소에서 다른 소 탐색
void bfs(int idx);
int main(void){
    int r1, c1, r2, c2;
    cin >> n >> k >> r;
    // 다리 저장하기
    for(int i = 0;i < r;i++){
        cin >> r1 >> c1 >> r2 >> c2;
        // 0: 상 / 1: 우 / 2: 하 / 3: 좌
        if(r1 == r2){
            if(c1 < c2){
                bridge[r1][c1][1] = 1;
                bridge[r2][c2][3] = 1;
            }
            else {
                bridge[r1][c1][3] = 1;
                bridge[r2][c2][1] = 1;
            }
        }
        else {
            if(r1 < r2){
                bridge[r1][c1][2] = 1;
                bridge[r2][c2][0] = 1;
            }
            else {
                bridge[r1][c1][0] = 1;
                bridge[r2][c2][2] = 1;
            }
        }
    }
    // 소 위치 저장하기
    for(int i = 1;i <= k;i++){
        cin >> r1 >> c1;
        cows.push_back({r1, c1});
        // 소의 인덱스를 맵에 표시. 단순히 1로만 표기 X. i로 표기
        farm[r1][c1] = i;
    }
    // BFS
    for(int i = 1;i <= k;i++){
        bfs(i);
    }

    for(int i = 1;i <= k;i++){
        for(int j = i + 1;j <= k;j++){
            if(meet[i][j] == 0) ans++;
        }
    }
    cout << ans;
}

bool inside(int r, int c){
    return r > 0 && r <= n && c > 0 && c <= n;
}

void bfs(int idx){
    // 방문 여부 저장
    int visit[101][101] = {0};
    queue<pair<int,int>> q;
    q.push({cows[idx - 1].first, cows[idx - 1].second});
    visit[cows[idx - 1].first][cows[idx - 1].second] = 1;
    while(!q.empty()){
        int row = q.front().first;
        int col = q.front().second;
        if(farm[row][col]) {
            // idx번째 소와 farm[row][col]에 위치한 소 연결
            meet[idx][farm[row][col]] = 1;
        }
        q.pop();
        for(int i = 0;i < 4;i++){
            if (bridge[row][col][i]) continue;
            // 다리를 쓰지 않고, 범위를 벗어나지 않고, 방문한 적 없는 칸으로 이동
            if(inside(row + dr[i], col + dc[i])){
                if(visit[row + dr[i]][col + dc[i]]) continue;
                q.push({row + dr[i], col + dc[i]});
                // 방문 처리
                visit[row + dr[i]][col + dc[i]] = 1;
            }
        }
    }
}