GALLERY(CCTV설치 문제) 질문드립니다. [자답 해결]

  • wans038
    wans038
    #include <iostream>
    #include <vector>
    
    using namespace std;
    
    vector<vector<int>> GS;
    vector<bool> visited;
    int cctvCount = 0;
    
    bool dfs2(int v, int depth)
    {
        visited[v] = true;
        const int size = GS[v].size();
    
        if (depth == 0 && size == 0) { ++cctvCount; return true; }
    
        bool isOk = false;
        for (int i = 0; i < size; ++i)
        {
            const int go = GS[v][i];
            if (!visited[go]) if (!dfs2(go, depth + 1)) isOk = true;
        }
        if (isOk)
        {
            ++cctvCount;
            return true;
        }
        return false;
    }
    
    /*
    https://algospot.com/judge/problem/read/GALLERY
    */
    int main()
    {
        ios::sync_with_stdio(false);
        int T;
        cin >> T;
        while (T-- > 0)
        {
            int G, H;
            cin >> G >> H;
            GS = vector<vector<int>>(G);
            visited = vector<bool>(G, false);
            for (int i = 0; i < H; ++i)
            {
                int u, v;
                cin >> u >> v;
                GS[u].push_back(v);
                GS[v].push_back(u);
            }
            for (int i = 0; i < G; ++i) if (!visited[i]) dfs2(i, 0);
            cout << cctvCount << endl;
            cctvCount = 0;
        }
        return 0;
    }
    

    CCTV 설치 문제 푸는 중 막혀서 질문드립니다.

    종만북에서 힌트를 얻어 트리의 잎 부터 CCTV 설치 여부를 검사했습니다.

    깊이가 0이고 자식이 없으면 노드 1개의 컴포넌트 이므로 무조건 CCTV를 설치하고

    dfs2 반환 값이 0이면 이전 노드에서 CCTV를 설치 안했으므로 현재 노드에서는 무조건 CCTV를 설치 해야 하므로 설치하고

    이런 방식으로 설계했습니다만...
    저의 실력으로 반례를 찾을 수 없겠네요...

    도움을 주시면 감사하겠습니다.

    2번째 작성코드(오답 코드)

    int V;
    vector<vector<int>> adj;
    vector<bool> visited;
    vector<bool> cctv;
    
    int dfs(int v)
    {
        visited[v] = true;
    
        vector<int> child;
        for (int i = 0; i < adj[v].size(); ++i)
        {
            const int go = adj[v][i];
            if (!visited[go])
            {
                const int x = dfs(go);
                child.push_back(go);
            }
        }
        for (auto i : child)
        {
            if (!cctv[i])
            {
                cctv[v] = true;
                break;
            }
        }
        return child.size();
    }
    
    int main()
    {
        ios::sync_with_stdio(false);
        int T;
        cin >> T;
        while (T--)
        {
            int E;
            cin >> ::V >> E;
            adj = vector<vector<int>>(V);
            visited = cctv = vector<bool>(V, false);
            for (int i = 0; i < E; ++i)
            {
                int u, v;
                cin >> u >> v;
                adj[u].push_back(v);
                adj[v].push_back(u);
            }
            for (int i = 0; i < V; ++i) if (!visited[i]) if(dfs(i) == 0) cctv[i] = true;
            int cctvCount = 0;
            for (int i = 0; i < V; ++i) if (cctv[i]) ++cctvCount;
            cout << cctvCount << endl;
        }
        return 0;
    }
    

    2주 전
1개의 댓글이 있습니다.
  • wans038
    wans038

    아... 정말 반례를 생각해보려고 계속 생각했습니다.
    저의 문제점은
    그냥 자식노드가 설치 되어있는지 아닌지 만 검사했기 때문입니다...

    반례 예제인데
    1
    6 5
    0 1
    1 2
    0 3
    3 4
    4 5

    0번 정점 기준으로 한쪽은 '설치됨', 다른 한쪽은 '감시당함'. 인데 '감시당함'은 저의 코드에서 '설치 안됨'으로 분류되기 때문에 한쪽이 설치되어있기 때문에 설치를 안해도되는데 '감시당함' 때문에 0번 정점을 설치하는 문제가 있었네요...ㅎ

    재미있는 문제 였습니다 ㅋㅋㅋ


    1주 전 link
  • 댓글을 남기시려면 로그인하세요.