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

문제 링크

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

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

 

문제

소가 길을 건너간 이유는 그냥 길이 많아서이다. 존의 농장에는 길이 너무 많아서, 길을 건너지 않고서는 별로 돌아다닐 수가 없다.

존의 농장에 대대적인 개편이 있었다. 이제 작은 정사각형 목초지가 N×N (2 ≤ N ≤ 100) 격자로 이루어져 있다. 인접한 목초지 사이는 일반적으로 자유롭게 건너갈 수 있지만, 그 중 일부는 길을 건너야 한다. 농장의 바깥에는 높은 울타리가 있어서 소가 농장 밖으로 나갈 일은 없다.

K마리의 (1 ≤ K ≤ 100,K ≤ N2) 소가 존의 농장에 있고, 각 소는 서로 다른 목초지에 있다. 어떤 두 소는 길을 건너지 않으면 만나지 못 할 수 있다. 이런 소가 몇 쌍인지 세어보자.

입력

첫 줄에 N, K, R이 주어진다. 다음 R줄에는 한 줄에 하나씩 길이 주어진다. 길은 상하좌우로 인접한 두 목초지를 잇고, r c r′ c′의 형태 (행, 열, 행, 열)로 주어진다. 각 수는 1 이상 N 이하이다. 그 다음 K줄에는 한 줄의 하나씩 소의 위치가 행과 열로 주어진다.

출력

길을 건너지 않으면 만날 수 없는 소가 몇 쌍인지 출력한다.

예제 입력 1

3 3 3
2 2 2 3
3 3 3 2
3 3 2 3
3 3
2 2
2 3

예제 출력 1

2

알고리즘 분류

• 그래프 탐색

풀이

먼저 길을 기록하기 위해 3차원 배열 Road[101][101][4]를 선언한다. 이는 (A, B) 목초지의 C번째 방향(북, 서, 남, 동)에 길이 있다는 뜻이다.

그리고 K마리의 소를 각각 BFS를 통해 경로를 기록한다. 소가 움직일 때 길이 있다면 그 곳으로는 가지 않는다.

이후 현재 소가 다른 소가 있는 곳까지 가지 못 한다면 반드시 길을 건너야지만 만날 수 있다는 것이 되므로, 해당 소들은 길을 건너지 않고서는 만날 수 없는 경우가 된다. 이런 소 쌍의 개수를 구해서 출력하면 끝이다.

코드

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#define MAX 101
#define INF 1e9
#define FASTIO cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

using namespace std;
int N, K, R, Y, X, Y1, X1;
int MAP[MAX][MAX];
bool Road[MAX][MAX][4];
bool Visited[MAX][MAX];
vector<pair<int, int> > Cow;
int MoveY[4] = { -1,0,1,0 };
int MoveX[4] = { 0,-1,0,1 };
int Answer = 0;

void init() {
    for (int i = 0; i < MAX; i++) {
        for (int j = 0; j < MAX; j++) {
            Visited[i][j] = false;
        }
    }
}

void input() {
    cin >> N >> K >> R;
    for (int i = 0; i < R; i++) {
        cin >> Y >> X >> Y1 >> X1;
        if ((Y - 1 == Y1) && (X == X1)) {
            Road[Y][X][0] = true;
            Road[Y1][X1][2] = true;
        }
        else if ((Y + 1 == Y1) && (X == X1)) {
            Road[Y][X][2] = true;
            Road[Y1][X1][0] = true;
        }
        else if ((Y == Y1) && (X - 1 == X1)) {
            Road[Y][X][1] = true;
            Road[Y1][X1][3] = true;
        }
        else if ((Y == Y1) && (X + 1 == X1)) {
            Road[Y][X][3] = true;
            Road[Y1][X1][1] = true;
        }
    }
    for (int i = 0; i < K; i++) {
        cin >> Y >> X;
        Cow.push_back(make_pair(Y, X));
    }
}

void BFS(int A, int B) {
    queue<pair<int, int> > Q;
    Visited[A][B] = true;
    Q.push(make_pair(A, B));

    while (!Q.empty()) {
        int NowY = Q.front().first;
        int NowX = Q.front().second;
        Q.pop();

        for (int i = 0; i < 4; i++) {
            int NextY = NowY + MoveY[i];
            int NextX = NowX + MoveX[i];
            if ((NextY >= 1) && (NextY <= N) && (NextX >= 1) && (NextX <= N) && !Visited[NextY][NextX]) {
                if (!Road[NowY][NowX][i]) {
                    Visited[NextY][NextX] = true;
                    Q.push(make_pair(NextY, NextX));
                }
            }
        }
    };
}

void settings() {
    for (int i = 0; i < Cow.size(); i++) {
        init();
        BFS(Cow[i].first, Cow[i].second);
        for (int j = i + 1; j < Cow.size(); j++) {
            if (!Visited[Cow[j].first][Cow[j].second]) {
                Answer++;
            }
        }
    }
}

void find_Answer() {
    cout << Answer << "\n";
}

int main() {
    FASTIO
    input();
    settings();
    find_Answer();

    return 0;
}