[백준 16724] 피리부는 사나이(C++)

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

문제설명

UDLR(상하좌우)로 각 칸에 있는 사람들이 어떤 방향에 있는지 주어진다. 사람들이 화살표를 따라 쭉 이동했을 때 모든 사람이 안전구역으로 들어갈 수 있도록 하려면 몇 개의 안전 구역을 만들어야 하는지를 묻는 문제이다.

아이디어

이 문제는 그래프의 사이클의 개수를 찾는 문제이다. 사이클 1개당 1개의 안전구역을 만들어 주면 된다. 그래서 dfs를 통해 그래프를 순회하며 부모(사이클의 시작점)를 기록해주고, 마지막에 부모가 총 종류가 있는지를 리턴해줬다.

아래의 경우 부모가 2종류가 나왔으니 2를 리턴해주면 된다.

코드

정답 코드는 아래와 같다. dfs를 이용해 순회하며 다음 블럭이 현재와 부모가 다르다면 Union함수를 통해 부모를 합쳐줬다. Union함수를 통해 부모를 합칠 때 둘 중 작은 값으로 통일해주고 싶은데 어떻게 구현할까 하다가 y좌표*가로길이+x좌표로 값을 비교해줬다. 

쉽게 말해 아래와 같이 칸별로 번호를 매긴 것이다. (물론 나는 좌측 상단좌표를 1,1로 잡아서 5부터 시작한다.)

1   2   3   4
5   6   7   8
9  10 11 12

#include <iostream>
#include <vector>
#include <set>
using namespace std;

char mp[1001][1001];
int parent[2002002];

int N, M;

int findParent(int child) {
    if (parent[child] != child)
        parent[child] = findParent(parent[child]);
    return parent[child];
}

void Union(int x, int y) {
    int rootX = findParent(x);
    int rootY = findParent(y);

    rootX < rootY ? parent[rootY] = rootX : parent[rootX] = rootY;
}

void dfs(int y, int x) {
    int curChar = mp[y][x];
    int nxtY, nxtX;

    if (curChar == 'U') {
        nxtY = y - 1;
        nxtX = x;
    }
    else if (curChar == 'D') {
        nxtY = y + 1;
        nxtX = x;
    }
    else if (curChar == 'R') {
        nxtY = y;
        nxtX = x + 1;
    }
    else {
        nxtY = y;
        nxtX = x - 1;
    }
    int curIdx = y * M + x;
    int nxtIdx = nxtY * M + nxtX;

    if (findParent(curIdx) != findParent(nxtIdx)) {
        Union(curIdx, nxtIdx);
        dfs(nxtY, nxtX);
    }

}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> N >> M;

    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            cin >> mp[i][j];
            parent[i * M + j] = i * M + j;
        }
    }

    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            if (findParent[i * M + j] == i * M + j){ 
                dfs(i, j); 
            }
        }
    }

    set<int> st;

    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            cout<<parent[i*M+j]<<" ";
            st.insert(parent[i * M + j]);
        }
        cout<<endl;
    }

    cout << st.size();
}

 

실수했던 부분

나는 이 문제를 여러 번 시도해서 맞췄는데, 자꾸 틀렸던 이유는 dfs를 할지 말지 판별할 때 자기 자신의 부모를 parent배열을 통해 확인했기 때문이었다. (findParent함수를 이용해야 한다.)

findParent함수를 통해 부모를 확인하지 않으면 parent배열이 제대로 초기화 되지 않는다. 이렇게 잘못 짜면 아래 예제를 통과할 수  없다.

입력
4 4
RRDD
RRUU
UULL
RRUU

정답: 2
출력: 3

틀렸던코드는 아래와 같다. (main함수만 발췌)

...

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> N >> M;

    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            cin >> mp[i][j];
            parent[i * M + j] = i * M + j;
        }
    }

    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            if (parent[i * M + j] == i * M + j){ //이부분을 findParent(i*M+j)로 고쳐야한다.
                dfs(i, j);
            }
        }
    }

    set<int> st;

    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            st.insert(parent[i * M + j]);
        }
    }

    cout << st.size();
}

 

parent배열을 이용해 부모를 찾았을 때와 findParent함수를 통해 부모를 찾았을 때의 차이점을 위 반례를 이용해 확인해보았다. 

좌측이 parent배열, 우측이 findParent함수를 사용했을 때의 parent배열 최종 값이다.

이런 차이는 18번 블럭(빨간 동그라미)에 도달했을 때 발생한다.

18번 블럭을 방문했을 때 findParent함수를 호출하면 해당 블럭의 값이 5로 바뀌게 된다. (17의 부모->5이기 때문) 그런데 단순히 parent배열을 이용해 값을 확인하면 18번 블럭의 부모값이 갱신이 안되어 결과적으로 틀린 답이 도출된다.

아래 그림을 보면 18번 블럭을 방문할 때 까지는 부모가 17이었는데 19번 블럭을 방문할 때는 5로 부모가 갱신된 것을 확인할 수 있다.

정답 코드 실행 시 parent배열

코드가 실행될 때 중간중간 parent배열을 확인하고 싶다면 아래 코드를 통해 확인할 수 있다.

#include <iostream>
#include <vector>
#include <set>
using namespace std;

char mp[1001][1001];
int parent[2002002];

int N, M;

int findParent(int child) {
    if (parent[child] != child)
        parent[child] = findParent(parent[child]);
    return parent[child];
}

void Union(int x, int y) {
    int rootX = findParent(x);
    int rootY = findParent(y);

    rootX < rootY ? parent[rootY] = rootX : parent[rootX] = rootY;
}

void dfs(int y, int x) {
    int curChar = mp[y][x];
    int nxtY, nxtX;

    if (curChar == 'U') {
        nxtY = y - 1;
        nxtX = x;
    }
    else if (curChar == 'D') {
        nxtY = y + 1;
        nxtX = x;
    }
    else if (curChar == 'R') {
        nxtY = y;
        nxtX = x + 1;
    }
    else {
        nxtY = y;
        nxtX = x - 1;
    }
    int curIdx = y * M + x;
    int nxtIdx = nxtY * M + nxtX;

    if (findParent(curIdx) != findParent(nxtIdx)) {
        Union(curIdx, nxtIdx);
        dfs(nxtY, nxtX);
    }

}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> N >> M;

    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            cin >> mp[i][j];
            parent[i * M + j] = i * M + j;
        }
    }

    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            cout<<"before: "<<i<<" "<<j<<" "<<i*M+j<<endl;
            for (int i = 1; i <= N; i++) {
                for (int j = 1; j <= M; j++) {
                    cout<<parent[i*M+j]<<" ";
                }
                cout<<endl;
            }
            if (parent[i * M + j] == i * M + j){ //이부분을 findParent(i*M+j)로 해야한다.
                cout<<"after\\n";
                for (int i = 1; i <= N; i++) {
                    for (int j = 1; j <= M; j++) {
                        cout<<parent[i*M+j]<<" ";
                    }
                    cout<<endl;
                }
                dfs(i, j);

            }
        }
    }

    set<int> st;
    
    cout<<"final\\n";
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            cout<<parent[i*M+j]<<" ";
            st.insert(parent[i * M + j]);
        }
        cout<<endl;
    }

    cout << st.size();
}