파이썬 알고리즘 190번 | [백준 13023번] ABCDE - DFS

190. ABCDE

1) 어떤 전략(알고리즘)으로 해결?

2) 코딩 설명

• dfs

<내 풀이>

import sys
sys.setrecursionlimit(10 ** 6)

n,m = map(int, sys.stdin.readline().rstrip().split())
# 사람의 수 / 친구 관계의 수 

node=[[] for _ in range(n)]
visited=[0 for _ in range(n)]
possible = False

def dfs(num, cnt) :
    global possible

    if possible : return
    if(cnt>=5) : possible = True; return

    for relation in node[num] :
        if visited[relation]==0:
            visited[relation]=1
            cnt+=1
            dfs(relation, cnt)
            visited[relation]=0
            cnt-=1

for i in range(m) : 
    a,b = map(int, sys.stdin.readline().rstrip().split())
    node[a].append(b) ; node[b].append(a)

for j in range(n) :
        visited[j]=1
        dfs(j, 1)
        visited[j]=0 # 꼭 다시 이렇게 원상복귀 시켜주기 
        
if possible : print(1)
else : print(0)

<내 틀렸던 풀이, 문제점>

시간초과

import sys
sys.setrecursionlimit(10 ** 6)
n,m = map(int, sys.stdin.readline().rstrip().split())
# 사람의 수 / 친구 관계의 수 
node=[[] for _ in range(n)]
visited=[0 for _ in range(n)]
maxcnt = -99999

def dfs(num, cnt) :
    global maxcnt
    for relation in node[num] :
        if visited[relation]==0:
            visited[relation]=1
            cnt+=1
            dfs(relation, cnt)
            visited[relation]=0
            cnt-=1
    else : 
        maxcnt= max(cnt, maxcnt)
        return
            

for i in range(m) : 
    a,b = map(int, sys.stdin.readline().rstrip().split())
    node[a].append(b) ; node[b].append(a)

for j in range(n) :
    if visited[j]==0:
        visited[j]=1
        dfs(j, 1)
        if(maxcnt>=5) : possible = True; break

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

10프로에서 틀렸습니다~

• 아래가 틀렸던 이유 :

DFS에는 가지 뻗을 때 다시 가지 뻗고 가지 뻗기 이전 상태로 돌려놔야하지

• DEF 안에서는 그렇게 잘 처리를 해찌
• 그렇지만 DEF 바깥에서 dfs 호출할 때 방문했던 것을 해지해주지 않았지
• visited=0 으로 되돌려놔야 하지

import sys
sys.setrecursionlimit(10 ** 6)

n,m = map(int, sys.stdin.readline().rstrip().split())
# 사람의 수 / 친구 관계의 수 

node=[[] for _ in range(n)]
visited=[0 for _ in range(n)]
possible = False

def dfs(num, cnt) :
    global possible

    if possible : return
    if(cnt>=5) : possible = True; return

    for relation in node[num] :
        if visited[relation]==0:
            visited[relation]=1
            cnt+=1
            dfs(relation, cnt)
            visited[relation]=0
            cnt-=1

for i in range(m) : 
    a,b = map(int, sys.stdin.readline().rstrip().split())
    node[a].append(b) ; node[b].append(a)

for j in range(n) :
    visited[j]=1 # 바로 이 부분을 다시 원상복구 해놓지 않아찌 
    dfs(j, 1)
        
if possible : print(1)
else : print(0)

<반성 점>

• dfs 이후 새로운 가지가 나간 후에 다시 원상복귀 잘 시켜놓자

<배운 점>

• 파이썬에서 dfs 재귀 쓸 때 맨 위에

sys.setrecursionlimit(10**6)

써야한다. 파이썬은 재귀가 최대 1000이기 때문