[백준] [DFS] [백트래킹] 13023. ABCDE

13023. ABCDE

13023번: ABCDE

 

• 내 풀이
  • 처음에 bfs로 풀었음 -> error
    • bfs로 돌면서 cnt[start] 증가시켰는데 그러면 여러 값들과 연결된값은 그 개수만큼 +1되서 잘못계산됨
  • 연결된 값들 백트래킹으로 원값 되돌려주면서 값 넘겨줘야 하기때문에 dfs + 백트래킹

def dfs(start,i, v):
    global result
    if v>=5:
      result=1
      return
      
    for gp in graph[i]:
        if visited[gp]==-1:
            visited[gp]=0
            dfs(start, gp, v+1)
            visited[gp]=-1
  

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

result=0
for i in range(n):
    visited = [-1 for _ in range(n)]
    visited[i]=0
    dfs(i,i,1)
    if result==1: break


if result==1:
    print(1)
else:
    print(0)