[DFS] BJ_13023, ABCDE

[문제의 접근]

 어떻게 이 문제에 접근할 수 있을까? 일단, 친구 관계로 주어지는 입력이 graph로 표시될 수 있다는 것을 알아야 한다. 또한 graph의 깊이가 4단계 까지만 진행할 수 있다면 문제의 답으로 도출할 수 있는 것으로 보아 그렇게 깊게 탐색할 필요가 없다는 사실도 알 수 있다. 모든 경우를 다 탐색해 봐야 하는 문제일까? 아니다. 5명이 친구가 되는 케이스가 하나만 있다면 탐색을 종료하고 답을 도출하면 된다. 그렇다면 어떤 알고리즘을 사용해야 할까? 바로 DFS이다. 

 

[DFS의 특징]

 탐색 가능한 경로의 모든 방향의 Graph를 탐색하여 답을 도출하는 BFS와는 다르게 DFS는 모든 경로를 체크하는 대신 한 경로 우선하여 마지막 깊이까지 진행하여 조건을 만족할 수 있다면 다른 경로를 탐색해 볼 필요없이 바로 종료 가능한 특징을 가지고 있다. 

 

[Graph 를 표현하는 방식]

 Graph를 표현하는 방식은 보통은 배열 array를 이용하여 표현한다. 하지만, graph의 입력 범위가 넓고 갯수는 크지 않다면 배열이 낭비되는 경향이 있어 dictionary도 사용하는 편이다. python에서는 dictionary로 구현하여 보았고, C++로는 vector<int>의 array로 선언하여 보았다. 두가지 방식을 비교해 볼 수 있을 것 같다. 

 Dictionary 구현 방식은 dictionary key가 존재하는지 확인하여 있으면 list에 append해주는 방식을 취하고, 없다면 해당 키에 새로운 list를 추가해 주는 방식으로 구현한다. key가 있는지 확인하기 위해서 dictionary.get()함수를 사용한다. list로 구현하는 경우는 C++ 코드에서 확인하는 것과 같이 key값의 입력범위에 해당하는 리스트를 모두 선언한 다음 해당 key array에 append하는 형식으로 진행하게 된다. 이는 DFS함수의 작동 방식에 index로 접근하느냐 key-value로 접근하느냐의 차이를 가져온다. 

 

< Python >

def input_data():
    graph = {}
    n, m = map(int, rdln().split())
    for _ in range(m):
        a, b = map(int, rdln().split())
        if graph.get(a):
            graph[a].append(b)
        else:
            graph[a] = [b]
        
        if graph.get(b):
            graph[b].append(a)
        else:
            graph[b] = [a]
    return n, m, graph

<C++>

vector<int> graph[_max];

for (int i=0; i<m;i++) {
        cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a); 
    }

[DFS 메인 코드]

 기본적으로 DFS 코드를 작성하는 논리는 Python, C++ 모두 동일하다. 다만, graph를 dictionary로 선언한 python의 경우는 아래와 같이 key - value로 접근해야 하기 떄문에 graph에 해당키가 존재하는지 확인하는 if graph.get(num) 구문이 꼭 필요하여 좀 번거로운 부분이 있고, C++은 index로 접근하기 떄문에 해당 index가 없다면 그대로 skip하게 되어 편리한 점이 있다. 범용적인 로직은 친구 관계를 4번 이상 확보하면 True return 시켜서 DFS를 종료하고 함수 내부에서도 DFS가 True를 반환하면 종료할 수 있도록 if dfs구문을 두어서 return 하게 작성한다. 한번 방문한 친구 관계는 재 방문할 필요가 없기 때문에 check배열을 이용해서 다시 재방문 하는 경우를 방지한다. 

 

<Python>

def dfs(num, cnt):
    if cnt >= 4:
        return True
    # graph 내부로 바로 접근하므로, key error방지 필요
    # size로 접근하면 조건을 뺄 수 있음.
    if graph.get(num):
        for nex in graph[num]:
            if check[nex]: continue
            check[nex] = 1
            if dfs(nex, cnt +1): return True
            check[nex] = 0
    return False

 <C++>

bool dfs(int num, int cnt) {
    if (cnt >=4) return true;
    // check[num] = True;
    
    // size로 접근하면 연결이 없을 시에 0이기 때문에 자동 기각됨
    for (int i =0;i<graph[num].size();i++){
        int nex = graph[num][i];
        if (check[nex]) continue;
        check[nex] = true;
        if (dfs(nex, cnt+1)) return true;
        check[nex] = false;
    }
    return false;
}

[Main 함수]

 Main함수에서의 주의점은 시작 노드인 i가 시작할 때마다 check 배열을 새롭게 0으로 갱신시켜줘야 한다는 점이다. 이 부분만 주의 해서 설정하고 dfs 초입에서 check[i]=1 시작점 설정한다면 문제 풀이는 종료된다. 

 

sol = 0
for i in range(n):
    check = [0]*2000
    check[i] = 1
    if dfs(i, 0): 
        sol = 1
        break

sys.stdout.write(f"{sol}\n")

 

<C++ 풀이> https://github.com/Koo82/Algotirhm/blob/main/%5BDFS%5DBJ_13023.cpp

<Python 풀이> https://github.com/Koo82/Algotirhm/blob/main/%5BDFS%5DBJ_13023.py