프로그래머스 - 양과 늑대 (dfs)

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

프로그래머스

1. 특징

dfs

 

2. 구현방법

1) dfs(현재노드, 양, 늑대, 다음에 방문할 수 있는 노드 벡터)

2) dfs 내부에서 현재 노드를 다음에 방문할 수 있는 노드 벡터에서 삭제해주고, 갈 수 있는 다음 노드(자식 노드)를 벡터에 추가해줌 -> dfs 다시 호출

 

3. 코드

#include <bits/stdc++.h>

using namespace std;
int s; 
int w;
int mx;
//dfs
vector<int> adj[20];

void dfs(int curnode, int s, int w, vector<int>& nxtnode, vector<int>& info)
{
    if(info[curnode] == 0) s++;
    else w++;
    
    if(w >= s) return;
    
    mx = max(mx, s);
    for(int i = 0; i < nxtnode.size(); i++)
    {
        vector<int> tmp = nxtnode;
        int x = nxtnode[i];
        tmp.erase(tmp.begin()+i);
        
        for(auto nxt: adj[x])
        {
            tmp.push_back(nxt);
        }
        dfs(x, s, w, tmp, info);
    }
}

int solution(vector<int> info, vector<vector<int>> edges) {
    int answer = 0;
    
    for(int i = 0; i < edges.size(); i++)
    {
        int u = edges[i][0]; int v = edges[i][1];
        adj[u].push_back(v);
    }
    
    vector<int> nxtnode;
    for(auto nxt: adj[0])
    {
        nxtnode.push_back(nxt);
    }
    
    dfs(0, 0, 0, nxtnode, info);
    answer = mx;
    
    return answer;
}

 

4. 참고 블로그

https://velog.io/@ddyy094/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EC%96%91%EA%B3%BC-%EB%8A%91%EB%8C%80-C-DFS

[프로그래머스] 양과 늑대 C++ - DFS