[백준][13023] - ABCDE 파이썬 PYTHON

[Gold V] ABCDE - 13023

문제 링크

13023번: ABCDE

성능 요약

메모리: 31256 KB, 시간: 700 ms

분류

백트래킹, 깊이 우선 탐색, 그래프 이론, 그래프 탐색

문제 설명

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을 출력한다.

🙋 문제 해석

먼저 이 문제는 그래프에서 특정조건을 만족 할 때 멈추면 되는데요,

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

라는 것은 깊이가 4면 멈추면 됩니다.
저는 bfs와 dfs중 dfs를 사용해서 문제를 풀었습니다.

 

---

🚫 TRY 01

import sys

input = sys.stdin.readline
def dfs(v,cnt):
    if cnt==4:
        print(1)
        exit()
    visited[v] = True
    for i in range(n):
        if visited[i] == False and graph[v][i] == 1 :
            dfs(i,cnt+1)
n,m = map(int,input().split())
graph = [[0]*n for _ in range(n)]
for i in range(m):
    a,b = map(int,input().split())
    graph[a][b]= graph[b][a] = 1
visited = [False] *n    
for i in range(n):
    dfs(i,0)
    visited = [False] *n
print(0)

먼저 처음에는 인접행렬을 이용해서, 문제를 풀었는데,

계속 오류가 납니다. 원래 그래프 문제는 bfs 인접행렬을 사용해서 자주 풀었는데.. 인정행렬은 간선이 많고 자주 비교해야하는 경우 유리하지만, 위와 같은 문제는 깊이가 4이면 바로 멈추어야 하기 때문에, 위와 같은 문제는 인접리스트가 시간복잡도가 낮다는 것을 확인하고 문제를 다시 풀었습니다.

🔑 Solution 🔑

import sys

input = sys.stdin.readline

def dfs(v, cnt):
    if cnt == 4:
        print(1)
        sys.exit()
    visited[v] = True
    for i in graph[v]: # 여기부터
        if not visited[i]:
            dfs(i, cnt+1)
    visited[v] = False

n, m = map(int, input().split())
graph = [[] for _ in range(n)] 
for i in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a) # 여기까지만 바꿨음..

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

print(0)

원래는 인접행렬만 사용했는데, 문제에 따라서 유동적으로 인접리스트도 사용해야 한다는 걸 알았습니다.

---

🙇