[파이썬(Python)] 백준 13023번 ABCDE - 그래프

 

 

백준 13023번: ABCDE

문제 바로 가기

---

📌 문제

BOJ 알고리즘 캠프에는 총 N명이 참가하고 있다. 사람들은 0번부터 N-1번으로 번호가 매겨져 있고, 일부 사람들은 친구이다.

오늘은 다음과 같은 친구 관계를 가진 사람 A, B, C, D, E가 존재하는지 구해보려고 한다.

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

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

입력

첫째 줄에 사람의 수 N (5 ≤ N ≤ 2000)과 친구 관계의 수 M (1 ≤ M ≤ 2000)이 주어진다.
둘째 줄부터 M개의 줄에는 정수 a와 b가 주어지며, a와 b가 친구라는 뜻이다. (0 ≤ a, b ≤ N-1, a ≠ b) 같은 친구 관계가 두 번 이상 주어지는 경우는 없다.

출력

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

 

 

 

 

 

 

 

 

 

 

📝 문제 분석

 

 

이 문제는 N명의 사람들과 M개의 친구 관계가 주어진 상황에서 특정한 친구 관계(A-B-C-D-E)가 존재하는지를 확인하는 문제입니다. 즉, 아래와 같은 친구 관계가 존재하는지 찾는 문제입니다.

• A는 B와 친구
• B는 C와 친구
• C는 D와 친구
• D는 E와 친구

 

이런 관계가 존재하면 1을 출력하고 존재하지 않으면 0을 출력해야 합니다. 

 

 

 

 

 

 

 

 

 

 

 

 

📃 예제 분석

 

📌 예제 1

5 4
0 1
1 2
2 3
3 4

0 - 1 - 2 - 3 - 4

👉 A-B-C-D-E 친구 관계가 존재하므로 1을 출력합니다. 

 

 

 

 

 

📌 예제 2

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

  0 - 1 - 2 - 3
  |   |
  4   3

👉 A-B-C-D-E 친구 관계가 있으므로 1을 출력합니다. 

 

 

 

 

 

📌 예제 3

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

      0
   // | \\
  1 2 3 4 5

👉 A-B-C-D-E 친구 관계가 없으므로 0을 출력합니다. 

 

 

 

 

 

 

 

 

 

 

💡 해결 방법

 

 

이 문제를 해결하기 위해 그래프 탐색 알고리즘을 사용해야 합니다. DFS를 활용하여 주어진 친구 관계가 존재하는지 확인할 수 있습니다. 

 

 

 

📌 DFS 탐색 과정

다음은 예제 1을 기준으로 한 DFS 탐색 과정입니다. 

 

1️⃣ 0번 사람에서 시작합니다.

0 - 1 - 2 - 3 - 4
↑
탐색 시작

 

2️⃣ 1번 친구를 방문합니다.

0 → 1

 

3️⃣ 2번 친구를 방문합니다.

0 → 1 → 2

 

4️⃣ 3번 친구를 방문합니다.

0 → 1 → 2 → 3

 

5️⃣ 4번 친구를 방문합니다.

0 → 1 → 2 → 3 → 4

 

6️⃣ 깊이가 4에 도달했으므로 1을 출력하고 종료합니다. 

• 깊이가 4에 도달하면 이미 5명이 친구 관계를 형성했음을 의미합니다. 

 

 

 

 

 

 

 

 

 

👩‍💻 나의 답안

 

 

1️⃣ 입력 및 그래프 구성

n, m = map(int, input().split())  # n: 사람 수, m: 친구 관계 수
relations = [[] for _ in range(n)]  # 각 사람의 친구 목록을 저장할 리스트

for _ in range(m):
    a, b = map(int, input().split())  # 친구 관계 입력 받기
    relations[a].append(b)  # a와 b는 친구
    relations[b].append(a)  # b와 a도 친구 (양방향 관계)

• n과 m을 입력받아 사람 수와 친구 관계 수를 저장합니다.
• relations 리스트를 생성하여 각 사람의 친구 관계를 저장합니다.
• 입력받은 (a, b) 쌍을 이용하여 무방향 그래프를 구성합니다.
• 양방향 관계이므로 relations[a].append(b)와 relations[b].append(a) 두 가지를 모두 추가합니다.

 

 

 

2️⃣ 친구 관계 정렬

for i in range(n):
    relations[i].sort()

• 각 사람의 친구 관계를 정렬합니다.

 

 

 

 

 

3️⃣ DFS 수행

visited = [False] * n  # 방문 여부를 체크하는 리스트

for i in range(n):  # 모든 사람을 시작점으로 DFS 수행
    visited[i] = True  # 현재 노드를 방문 처리
    dfs(i, 0)  # DFS 실행 (깊이 0부터 시작)
    visited[i] = False  # 백트래킹 (방문 해제)

• visited 리스트를 이용해 각 친구 관계의 방문 여부를 체크합니다. 
• 모든 사람을 시작점으로 DFS를 실행합니다. 
• 탐색이 끝나면 백트래킹을 수행하여 방문 상태를 원래대로 되돌립니다. 

 

 

 

 

 

4️⃣ DFS 함수

def dfs(node, depth):
    if depth == 4:  # 깊이가 4에 도달하면 5명의 연속된 친구 관계가 형성됨
        print(1)
        sys.exit()  # 프로그램을 즉시 종료 (더 이상 탐색할 필요 없음)
    
    for friend in relations[node]:  # 현재 노드와 연결된 친구 탐색
        if not visited[friend]:  # 방문하지 않은 친구만 탐색
            visited[friend] = True  # 방문 처리
            dfs(friend, depth + 1)  # 깊이를 1 증가시키며 DFS 탐색
            visited[friend] = False  # 백트래킹 (다른 경로를 탐색하기 위해 방문 해제)

• 현재 depth가 4에 도달하면 주어진 5개의 친구 관계가 성립하므로 1을 출력하고 종료합니다.
• 현재 사람의 모든 친구 관계를 탐색하며 방문하지 않은 경우에만 탐색을 진행합니다. 
• DFS 호출 후 다른 경로를 탐색할 수 있도록 방문 처리를 False로 되돌려 백트래킹을 수행합니다. 

 

 

 

 

 

5️⃣ 탐색 종료

print(0)

• 만약 모든 탐색이 끝났는데도 주어진 친구 관계가 존재하지 않는다면 0을 출력합니다.
• 이는 모든 가능한 경로를 확인했음에도 조건을 만족하는 경로가 없음을 의미합니다.

 

 

 

 

 

🚀 전체 코드 

import sys

def dfs(node, depth):
    if depth == 4:
        print(1)
        sys.exit()
    
    for friend in relations[node]:
        if not visited[friend]:
            visited[friend] = True
            dfs(friend, depth+1)
            visited[friend] = False



n, m = map(int, input().split())
relations = [[] for _ in range(n)]

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

for i in range(n):
    relations[i].sort()

visited = [False] * n

for i in range(n):
    visited[i] = True
    dfs(i, 0)
    visited[i] = False

print(0)

 

Algorithm/백준/Gold/13023. ABCDE at main · kuun1000/Algorithm