[프로그래머스] 2022 카카오 공채 양과 늑대 C++ 풀이

https://programmers.co.kr/learn/courses/30/lessons/92343

코딩테스트 연습 - 양과 늑대

 

2022 KAKAO BLIND RECRUITMENT 양과 늑대 문제 C++ 풀이입니다.

 

 

필요한 배경지식

• BFS, 비트마스킹

 

 

문제 해결 방법

그래프나 트리문제에서 BFS나 DFS을 풀이방법으로 생각해 볼 수 있는데,

이 문제는 단순 BFS또는 DFS로는 풀 수 없는 문제이다.

 

위 그림에서 BFS풀이를 생각해 보면, 0번과 1번 노드를 방문한 후에는 8번노드로 갈 수 있지만, 0번노드에서 시작해 바로 8번으로 갈 수는 없다. 즉, 방문했던 노드에 따라서 방문할 수 있는 노드가 달라지기 때문에 어떤 노드를 방문했는지에 따라 다른 상태를 가지게 되는 것이다.

 

다음으로 DFS와 백트래킹을 이용한 풀이를 생각해 보자.

DFS로 탐색하면서 상태를 변경시키고 다음으로 갈 수 있는 노드를 탐색하는 방법이다.

위 그림에서 예를 들면, 0번 노드를 방문한 상태에서는 1번과 8번 노드를 방문할 수 있는지 고려해볼 수 있고

0번과 1번 노드를 방문한 상태에서는 2번, 4번 그리고 8번 노드를 방문할 수 있는지 고려해볼 수 있다.

 

이렇게 하면 모든 상태를 고려할 수 있기 때문에 문제를 풀 수 있을것 같지만,

탐색하는 과정에서 상태를 중복으로 탐색하기 때문에 시간복잡도가 기하급수적으로 늘어나게 되는 문제가 생긴다.

(해당 문제에서는 테케가 빈약하여 이처럼 구현해도 통과할 수는 있음.)

 

하나의 예시를 들어보자면,

0,1,7,8번 노드를 방문한 상태에서 9번 노드를 방문하여 0,1,7,8,9를 방문한 상태와

0,1,8,9번 노드를 방문한 상태에서 7번 노드를 방문하여 0,1,7,8,9를 방문한 상태는 같은 상태라는 것을 알 수 있다.

그 전에 0,1,7,8 방문상태 또는 0,1,8,9 방문상태도 중복하여 탐색되었을 수도 있을 것이다.

그렇다면 최악의 경우 얼마나 많은 상태들이 2번, 4번, 8번, 16번...... 만큼 중복하여 탐색이 될까 ?

 

따라서 이러한 상태의 중복 탐색 문제를 해결하기 위해 메모이제이션 처리를 해야 하는데, 비트마스킹을 이용하여 해당 문제를 해결했다. 비트마스크를 이용하여 다음 상태를 탐색할때 방문한 비트인지 확인해주면 중복탐색 문제를 해결할 수 있다. 이때, 해당 배열을 이용하여 모든 상태를 표현할 수 있기 때문에 BFS로도 해결이 가능하다. 노드를 방문처리하는 배열에 차원을 하나 늘려 상태에 대한 정보와 함께 방문처리를 해주면 된다.

 

 

 

C++ 코드

• BFS + 비트마스킹 풀이

#include<bits/stdc++.h>
#define xx first
#define yy second
using namespace std;
using pii = pair<int,int>;
using dpii = pair<pii,pii>;

int N;
int m[17]{}; // 양,늑 정보
vector<int> adj[17]{}; // 그래프
int vi[1<<17][17]{}; // 방문여부. vi[a][b] : 방문한 노드의 정보가 담긴 비트a, 현재 위치한 노드b

int bfs(){
    int res = 1; // 최대 양 개수
    queue<dpii> q;
    q.push({{1,0},{1,0}}); // {비트마스크, 현재노드}, {양 개수, 늑대 개수}
    vi[1][0] = true;
    
    while(!q.empty()){
        int cmask = q.front().xx.xx;
        int cnode = q.front().xx.yy;
        int csheep = q.front().yy.xx;
        int cwolf = q.front().yy.yy;
        q.pop();
        
        for(auto next : adj[cnode]){
            if(cmask & (1<<next)){ // 다음 노드를 방문한 적이 있음
                if(vi[cmask][next]) continue; // 방문처리 되어 있으면 continue
                q.push({{cmask,next}, {csheep,cwolf}});
                vi[cmask][next] = true;
            } else { // 다음 노드를 방문한 적이 없음
                int nmask = cmask | (1<<next);
                if(m[next]==0) { // 다음 노드가 양일때
                    q.push({{nmask,next}, {csheep+1,cwolf}});
                    vi[nmask][next] = true;
                    res = max(res, csheep+1);
                } else { // 다음 노드가 늑대일때
                    if(csheep <= cwolf+1) continue; // 조건 처리
                    q.push({{nmask,next}, {csheep,cwolf+1}});
                    vi[nmask][next] = true;
                }
            }
        }
    }
    
    return res;
}

int solution(vector<int> info, vector<vector<int>> edges) {
    N = info.size();
    for(int i=0; i<N; i++) m[i] = info[i];
    for(int i=0; i<edges.size(); i++){ // 그래프의 인접리스트 초기화
        int a = edges[i][0];
        int b = edges[i][1];
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    
    return bfs();
}