[BOJ] 13023. ABCDE (🥇, BFS/DFS)

🔗

풀이

🧐 뭘 구하는 문제인가?

친구 관계는 대표적인 그래프 탐색 문제 중 하나다. 너비 우선 탐색(BFS)과 깊이 우선 탐색(DFS)이라는 아주 유명한 알고리즘 기법들이 있다. 어떤 문제들은 두 가지 중 어떤 방식을 택해도 풀리겠지만 어떤 문제는 둘 중 하나의 방법을 택하는 것이 훨씬 효율적일 때가 있다. 이 문제도 그런 문제 유형 중 하나다.

이 문제에서 구해야 하는 것은 무엇일까?

A → B → C → D → E 의 관계를 묻고 있다. 그래프 탐색 용어로 말하면 깊이4 이상인 노드가 존재하느냐의 문제가 될 수 있다. 즉, 이 문제는 이 그래프의 깊이를 구하는 문제이다. DFS로 풀어야 한다

🥲 어떻게 구현해야 할까?

백준의 텀 프로젝트 문제를 풀었더니 이 문제도 사이클에 국한돼서만 생각하게 됐다. 아래의 테스트 케이스 같은 경우도 모든 노드들이 하나의 사이클에 들어있지만 시작 노드가 어디인가에 따라 찾을 수 있는 깊이가 다르다

0에서 시작하면 0 → 1 → 2 → 3 → (0) 중복되는 관계 때문에 깊이 3까지 밖에 찾지 못한다.

하지만 4에서 시작하면 4 → 1 → 2 → 3 → 0 순서로 깊이 4의 관계를 찾을 수 있다.

5 5
0 1
1 2
2 3
3 0
1 4

결국 하나의 사이클을 이룬다고 해서 그 사이클 내의 어느 지점에서 시작하든 동일한 깊이를 찾을 수 있는 게 아닌 것이다. 모든 노드에 대해서 현재 노드에서 출발했을 때 깊이4까지 들어갈 수 있는지 여부를 확인해야 한다.

❌ 실패 코드

무조건 0번 노드에서 시작되는 코드였다. 장렬하게 실패했다.

# ABCDE

N, M =  map(int, input().split())
graph = [[] for _ in range(N+1)]

for _ in range(M):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

friend = set()
def dfs(i, depth):
    if depth == 4:
        return True
    
    friend.add(i)
    for x in graph[i]:
        if x not in friend and dfs(x, depth+1):
            return True
    friend.remove(i)

    return False

print(int(dfs(0, 0)))

⭕️ 성공 코드

깊이 4를 찾으면 그 즉시 True를 반환한다. 함수의 결과 값이 True 경우 True를 반환할 수 있도록 재귀로 구현했기 때문에 깊이 4인 곳을 한 번이라도 찾으면 이 재귀 함수는 전체적으로 True를 반환하게 된다.

어떤 노드에서든지 한 군데라도 True를 반환하는 곳이 있으면 바로 1을 반환할 수 있도록 sol() 함수를 구현했다.

# ABCDE

N, M =  map(int, input().split())
graph = [[] for _ in range(N)]
visited = [False]*(N)

for _ in range(M):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

def dfs(i, depth):
    if depth == 4:
        return True
    
    visited[i] = True
    for x in graph[i]:
        if not visited[x] and dfs(x, depth+1):
            return True
    visited[i] = False

    return False

def sol():
    for i in range(N):
        if dfs(i, 0):
            return True
    return False

print(int(sol()))