[백준/Python(파이썬)] 13023 ABCDE

2021-02-04

문제 : https://www.acmicpc.net/problem/13023

13023번: ABCDE

처음에는 문제를 잘못읽어서 ABCDE가 사이클을 이루는 줄 알고 사이클을 이루는 그래프를 찾고있었는데 그게 아니었다...

모든 그래프가 ABCDE처럼 일렬로 연결되어있어야 하는 문제인줄 알았는데 그것도 아니었고 그냥 깊이가 4 이상인 그래프를 찾는거였음..

전부 다 일렬로 연결된 그래프를 찾는거면 예제 중에서 불가능한 경우가 있어서 저 예시는 왜있는건지 고민을 했었지만..내가 잘못풀고있었던거였다..

오늘 종만북에서 그래프 부분 공부하고 와서 풀어본 문젠데 그래프 짜는거보다 문제 해독을 못하고 있었다

https://www.acmicpc.net/workbook/view/3938

문제집: SW 역량 테스트 준비 - 기초 (code.plus)

여기 문제집에 있는 그래프 문제 다 풀어보려고 함 이미 풀었던 문제도 있는데 푼지 너무 오래되서 다시 풀어서 올려야겠다

 

[소스코드]

https://github.com/jisun1125/algorithm-problem-solving/blob/main/baekjoon/no_13023.py

jisun1125/algorithm-problem-solving

finished = False
visited = [False]*2001
def dfs(here, depth):
    global finished

    visited[here] = True
    if depth == 4:
        finished = True
        return
    for i in f[here]:
        if not visited[i]:
            dfs(i, depth+1)
            visited[i] = False  # dfs에서 빠져나왔다는건 제일 안쪽까지 파고들었다가 다시 나오는 것이기 때문에 방문표시를 풀어줌

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

for i in range(n):
    dfs(i, 0)
    visited[i] = False
    if finished:
        break
if finished:
    print(1)
else:
    print(0)