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

문제

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

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

접근

 문제를 잘 못 이해하기 쉬운 문제이다. 문제를 좀 더 쉽게 풀어서 이야기해보자면 일반적으로 소는 현재 위치에서 인접한 상, 하, 좌, 우로 이동할 수 있다. 하지만 그중에서 일부는 벽으로 막혀있어서 다리를 만들어서 다리로만 이동할 수 있다. 이때 다리의 개수는 R로 주어지며 입력은 다리로 이어지는 두 좌표를 준다. 즉, 입력으로 2 2 2 3을 입력받았다면 (2, 2)에서 (2, 3)으로 가는 길목에는 다리가 설치되어 있다는 뜻이다. 이 경우 (2, 2)의 기준으로는 우(오른쪽)로 이동하는 길에 다리가 설치된 것일 테고, (2, 3)의 기준으로는 좌(왼쪽)로 이동하는 길에 다리가 설치되었을 것이다. 따라서 이런 다리의 설치 여부를 map[105][105][5] 과 같은 3차원 배열로 저장해주었다. 이 3차원 배열에는 임의의 좌표(x, y)에 소가 존재하는지와 현재 좌표에서 상, 하, 좌, 우에 다리가 설치되어 있는지를 저장해 주었다. 즉, 임의의 소가 다른 소에게 가는 방법 중 다리를 건너지 않으면 만날 방법이 없다면 이 문제에서 답으로 요구하는 '길을 건너지 않으면 만날 수 없는 소'이다. 

 길을 건너지 않으면 만날 수 없는 소를 구하기 위해 현재 맵 위에 존재하는 모든 소를 기준으로 각각 BFS를 돌려보았으나 시간 초과가 났다. 조금만 생각해보면 임의의 소 A가 BFS를 돌며 만난 소 B는 다시 BFS를 돌아줄 필요가 없다. 왜냐하면 A가 다리 때문에 만나지 못한 소는 B 또한 똑같이 만나지 못하기 때문이다. 즉, BFS를 돌면서 만나는 소는 chk[105][105] 배열에 체크해주고, 따로 그 수도 세어줬다가(cow_counter) 마지막에 한 번에 계산해 주면 된다. 

 

+ 메모리와 시간이 괜찮게 나와서 등수를 보니 1등이어서 놀랐다. 많은 사람이 도전한 문제에서 가장 효율성 있게 짰다는 뜻이니까 뿌듯하기도 하고,.. 어쨌든 어떤 문제에서 1등을 받아본 건 처음이라 기념으로 남겨본다 ㅎㅎ

코드

#include <iostream>
#include <queue>

using namespace std;

int main() {
    ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

    int N, K, R, a, b, c, d, ans = 0, dx[] = {0, 0, -1, 1}, dy[] = {-1, 1, 0, 0};
    bool map[105][105][5] = {0}, chk[105][105] = {0}; // map -> 0 : 왼, 1 : 오, 2 : 위, 3 : 아래, 4 : 소(cow)
    cin >> N >> K >> R;

    for (int i = 0; i < R; i++) {
        cin >> a >> b >> c >> d;
        if (a == c && b > d) {
            map[a][b][0] = 1;
            map[c][d][1] = 1;
        } else if (a == c && b < d) {
            map[a][b][1] = 1;
            map[c][d][0] = 1;
        } else if (a > c && b == d) {
            map[a][b][2] = 1;
            map[c][d][3] = 1;
        } else {
            map[a][b][3] = 1;
            map[c][d][2] = 1;
        }
    }
    for (int i = 0; i < K; i++) {
        cin >> a >> b;
        map[a][b][4] = 1;
    }
    
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            if (map[i][j][4] == 0 || chk[i][j] == 1)
                continue;
            int cow_counter = 1; // 자기 자신
            bool visit[105][105] = {0};
            visit[i][j] = 1;
            queue<pair<int, int>> q;
            q.push({i, j});
            while (!q.empty()) {
                pair<int, int> f = q.front();
                q.pop();
                for (int i = 0; i < 4; i++) {
                    if (map[f.first][f.second][i] == 1)
                        continue;
                    int newx = f.first + dx[i];
                    int newy = f.second + dy[i];
                    if (newx < 1 || newx > N || newy < 1 || newy > N || visit[newx][newy] == 1)
                        continue;
                    if (map[newx][newy][4] == 1) {
                        chk[newx][newy] = 1;
                        cow_counter++;
                    }
                    q.push({newx, newy});
                    visit[newx][newy] = 1;
                }
            }
            ans += (K - cow_counter) * cow_counter;
        }
    }
    cout << ans / 2;
    return 0;
}

 

깃 허브 주소 : https://github.com/algoribi/algorithm-study