[백준] 13023번 ABCDE(python)

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

13023번: ABCDE

 

1. 내가 작성한 코드(틀림)

import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

def dfs(v):

  for i in relation[v]:
    if visit[i] == 0:
      visit[i] = visit[v] + 1
      dfs(i)
    

n,m = map(int, input().rstrip().split()) #n=친구수 m=관계수

relation = [[] for _ in range(n)]

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

matrix = [0 for i in range(n)]
check = 0

while 0 in matrix:

  for i in range(n):
    visit = [0] * n
    if matrix[i] == 0:
      matrix[i] = 1
      visit[i] = 1
      dfs(i)
      print(visit)
      if (max(visit)-1) >= 4:
        check = 1
        print(1)
        exit()
        
print(0)

dfs 방식을 이용해서 해결하려고 했다.

 

그런데 계속 44퍼센트에서 오류 😥 

 

질문게시판에 있는 반례를 찾아보니 

 

0->1

1->3 #얘를 삭제해줘야됨

1->4

4->3

3->2

 

answer = 1

 

그러나 1->3을 계속 방문하여 출력이 0이 되는 상황이었다.

 

내 코드는 4->3을 방문할 경우 이미 방문처리가 되어있어서 최대값이 제대로 올라가지 않아서 오류가 발생한 것

 

따라서 재귀호출이 끝나고 visit[i]의 값을 0으로 바꿔주어야 했다.

 

이걸 해결할 방법을 찾지 못하고 결국 구글링,,

 

import sys
sys.setrecursionlimit(10**9)

def dfs(v,cnt):
  if cnt == 4:
    print(1)
    exit()
  for i in relation[v]:
    if visit[i] == 0:
      visit[i] = 1
      dfs(i, cnt+1)
      visit[i] = 0
    

n,m = map(int, input().rstrip().split()) #n=친구수 m=관계수

relation = [[] for _ in range(n)]

visit = [0] * n

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

for i in range(n):
  visit[i] = 1
  dfs(i,0)
  visit[i] = 0
        
print(0)

 

이 문제의 난이도는 크게 높지 않았는데, 아이디어를 생각하기 어려워서 너무너무너무 시간이 오래걸렸다 ㅠ

 

그래프 한 바퀴 돌리고 다시 복습하기

 

3. 메모

exit() => 프로그램 종료