[백준] 13023 ABCDE

문제 출처: 백준 온라인 저지 13023 ABCDE

13023번: ABCDE

 

문제 설명

🔎BOJ 알고리즘 캠프에는 총 N명이 참가하고 있다. 사람들은 0번부터 N-1번으로 번호가 매겨져 있고, 일부 사람들은 친구이다.
오늘은 다음과 같은 친구 관계를 가진 사람 A, B, C, D, E가 존재하는지 구해보려고 한다.

A는 B와 친구다.
B는 C와 친구다.
C는 D와 친구다.
D는 E와 친구다.

위와 같은 친구 관계가 존재하는지 안하는지 구하는 프로그램을 작성하시오.

(문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다.)

위 그림에서 나타난 것 처럼, 주어진 여러 관계 속에서 A➡B➡C➡D➡E 로 이어지는 관계가 존재하는지 묻는 문제이다.

해당 관계가 몇번이 나타나는지는 상관없이 하나라도 존재하면 1, 하나도 존재하지 않는다면 0을 출력한다.

 

문제를 읽기만 했을 때는 그래프 문제라고 파악하기 힘들지만, 주어진 예제들을 통해 그래프 탐색을 통해 문제를 해결해야하는 것을 확인할 수 있다.

입력 예제	출력 예제
5   4 0   1 1   2 2   3 3   4	1

 

<정답 코드>

def dfs(cur, depth=0):
    if depth == 4:
        return True

    visit[cur] = True

    for nx in relation[cur]:
        if not visit[nx]:
            flag = dfs(nx, depth+1)
            if flag:
                return True

    visit[cur] = False
    return False


n, m = map(int, input().split())
relation = [[] for _ in range(n)]
ans = 0
for _ in range(m):
    v, w = map(int, input().split())
    relation[v].append(w)
    relation[w].append(v)


for i in range(n):
    visit = [False] * n
    ans = dfs(i)
    if ans:
        break

print(int(ans))

한번만 관계를 확인하면 되기에 flag와 DFS를 활용해 문제를 풀이하였다.

접근은 아래와 같다.

 

1. 입력을 2차원 리스트에 그래프형태로 저장한다.

2. 그래프를 dfs를 통해 순회한다. dfs를 수행할 때는 depth 인자를 주어 depth가 4가 되면 탈출하게 작성하였다.

3. depth가 4일 때만 True를 반환하여 flag를 변경해주었고, flag가 True가 되면 True를 반환하며 탈출한다.

 

dfs의 특성을 통해 깊이 = 관계의 깊이로 생각하여 문제를 풀었다.

주의해야할 점은 탐색에 실패하였을 때 visit[cur]을 False로 바꾸어 다음 진행에 차질이 생기지 않도록 하는 것이다.