[C++/PGS] Lv.3 : 양과 늑대 (DFS)

 

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

프로그래머스

---

프로그래머스 레벨 3.

꽤나 까다로웠던 문제 👿

탐색 시 조건이 있으므로, dfs 백트래킹을 적용한다.

근데 백트래킹은.. 안해도 된다 (단방향 그래프이고, 방문 체크가 없음)

 

DFS에 현재 인덱스, 양의 수, 늑대의 수, 그리고 현재 위치에서 갈 수 있는 다음 노드 목록을 전달하면

연결된 다음 노드를 방문하고

조건에 맞지 않으면 재귀를 중단하고 반환한다.

 

bfs로 푸는 방법도 있던데, 그건 아래의 링크를 참고하면 될 듯하다.

너비우선 탐색으로 풀 때는 백트래킹이 필요한 것 같아서 오히려 깊이우선 탐색 풀이가 더 직관적인 느낌이다..!

질문하기 게시판의 bfs 풀이 : https://school.programmers.co.kr/questions/81369

 

 

 

나의 풀이

#include <string>
#include <vector>
#include <iostream>
#include <map>
using namespace std;

int graph[18][18] = {0,};
vector<vector<int>> edges;
vector<int> info;
map<int, vector<int>> m;
int answer = 0;
int sheepCount = 0;

void dfs(int index, int sheep, int wolf, vector<int> canGo){
    if(sheep <= wolf) return;
    if(sheep == sheepCount) {
        answer = sheep; return;
    }
    if(answer<sheep) answer = sheep;
    
    for(int node: m[index]){ // 갈 수 있는 노드 탐색
        canGo.push_back(node);
    }
    for(int i=0; i<canGo.size(); ++i){
        vector<int> newGo = canGo;
        newGo.erase(newGo.begin()+i);
        // 현재 노드만 삭제(중복방지), 다른 노드는 방문가능하므로 남겨야 함
        if(info[canGo[i]]==0) dfs(canGo[i], sheep+1, wolf, newGo);
        else dfs(canGo[i], sheep, wolf+1, newGo);
    }
}

int solution(vector<int> i, vector<vector<int>> e) {
    // 백트래킹?
    edges = e;
    info = i;
    for(auto edge : e){
        m[edge[0]].push_back(edge[1]);
    }
    for(int n: i){
        if(n==0) sheepCount++;
    }
    vector<int> canGo; // 갈 수 있는 자식노드 목록
    dfs(0,1,0,canGo);
    return answer;
}