[DFS] 양과 늑대 - 2022 KAKAO BLIND RECRUITMENT

해결 방법

사실상 모든 경로를 다 따져봐야 하는 문제다. 물론, 양과 늑대의 수가 같아지는 시점부터는 해당 경로에 대한 dfs는 중단해야 한다.

필자는 현재까지의 방문 노드들을 하나의 통합 노드로 두고, 통합 노드의 인접 노드들을 하나씩 방문해나가는 방법으로 해결했다. 시작 정점에서 정점을 추가해가며 단계적으로 트리를 확장한다는 접근법만 놓고 보면 프림 알고리즘과 비슷한 느낌이 들지 않는가? 물론 간선의 비용도 없고 dfs이기 때문에 방문을 취소해야 할 때가 있다는 차이점이 있기는 하다.

인접노드를 방문했을 때 양과 늑대의 수가 같아지거나 더 이상 방문할 노드가 없다면 해당 경로에 대한 dfs를 중단하면서 방문도 취소해주면 된다.

 

 

소스 코드

#include <vector>
using namespace std;

vector<int> v[17] // 간선 벡터
vector<int> _info; // info 배열 복사본
bool visited[17]; // 방문 벡터
int answer=-1;

void dfs(vector<int> cur, int balance, int sum) {
    if(balance==0) return;
    answer=max(answer, sum);
    int nxt;
    for(int i=0;i<cur.size();i++) {
        for(int j=0;j<v[cur[i]].size();j++){
            nxt=v[cur[i]][j]; // 방문 예정 노드
            if(visited[nxt]) continue; // 이미 방문한 노드는 탐색하지 않음
            
            // 방문 처리
            cur.push_back(nxt);
            visited[nxt]=true;
            balance+=_info[nxt]; // balance : 양의 수 - 늑대의 수
            if(_info[nxt]==1) sum++; // 총 양의 수
            
            // dfs 수행
            dfs(cur, balance, sum);
            
            // 방문 취소
            cur.pop_back();
            visited[nxt]=false;
            balance-=_info[nxt];
            if(_info[nxt]==1) sum--;
        }
    }
}

int solution(vector<int> info, vector<vector<int>> edges) {
    for(int i=0;i<info.size();i++) _info.push_back(info[i]?-1:1); // 양을 1, 늑대를 -1로 치환
    for(int i=0;i<edges.size();i++) v[edges[i][0]].push_back(edges[i][1]);
    vector<int> cur;
    visited[0]=true;
    cur.push_back(0);
    dfs(cur, 1, 1);
    return answer;
}

 

테스트케이스 18개 모두 정답

 

문제 출처 : https://school.programmers.co.kr/learn/courses/30/lessons/92343