[백준] 13023번 : ABCDE - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트

 

13023번: ABCDE

 

1. 문제 설명

2. 풀이과정

N의 최대 범위가 2,000이므로 알고리즘의 시간 복잡도를 고려할 때 조금은 자유롭다.

문제에서 요구하는 A, B, C, D, E의 관계는 재귀 함수의 형태와 비슷하기 때문에 주어진 모든 노드에 DFS를 수행하고 재귀의 깊이가 5 이상(5개의 노드가 재귀 형태로 연결)이면 1, 아니면 0을 출력한다.

DFS의 시간 복잡도는 O(V + E)이므로 최대 4,000, 모든 노드를 진행했을 때 4,000 * 2,000 즉, 8.000.000이므로 DFS를 사용해도 제한 시간 내에 문제를 해결할 수 있다.

 

그래프 데이터를 인접 리스트로 저장하고 모든 노드에서 DFS를 수행한다.

수행할 때 재귀 호출마다 깊이를 더하여 깊이가 5가 되면 1을 출력하고 프로그램을 종료한다.

모든 노드를 돌아도 1이 출력되지 않는다면 0을 출력한다.

 

슈도코드

1. N(노드 개수), M(에지 개수, 관계 개수) 입력받기
2. li(그래프 데이터 저장할 인접 리스트) 생성
3. for M의 개수만큼 반복: li 인접 리스트에 그래프 데이터 입력받아 저장
4. visited(방문 기록 저장 리스트) 생성
5. finish(종료 확인 변수)
6. DFS(현재 노드, 깊이):
   1. if (깊이 == 5): finish = True, 종료
   2. 방문 리스트에 현재 노드 방문 기록
   3. 현재 노드의 연결 노드 중 방문하지 않은 노드로 DFS 실행 (호출마다 깊이 1씩 증가)
7. for N의 개수만큼 반복:
   1. 노드마다 DFS 실행
   2. if (finish) 반복문 종료
8. if (finish): 1 출력
9. else: 0 출력

반응형

3. 소스코드

import sys

N, M = map(int, sys.stdin.readline().split())

li = [[] for _ in range(N + 1)]
for _ in range(M):
    v1, v2 = map(int, sys.stdin.readline().split())
    li[v1].append(v2)
    li[v2].append(v1)

visited = [False] * (N + 1)
finish = False

def DFS(n, d):
    global finish
    if (d == 5):
        finish = True
        return
    
    visited[n] = True
    for i in li[n]:
        if (not visited[i]):
            DFS(i, d + 1)

    visited[n] = False

for i in range(N):
    DFS(i, 1)
    if (finish):
        break

if (finish):
    print(1)
else:
    print(0)