백준_13023_ABCDE(python)

# 문제에서 예를 든 것이 꼬리에 꼬리를 물고 있는 것이 4개 있었기에 예제 2번을 봤을 때 왜 1인지 몰랐다.

# 혹시 친구의 친구가 나와도 친구인 건가라는 생각이 들었지만 예제 3에서 아니라고 말을 해주었다.

# 그렇다면 왜 예제2는 1인거지? 여기서 한 번 반례를 생각을 하고 아니었으면 문제에서 이해한 것이 맞다고 생각을 하고

   다시 처음으로 돌아와서 생각을 했어야 됐는데 뇌가 비벼져서 혼자 예제를 만들기 시작했다.

# 결국 예제2만 이해하는데 약 1시간을 쏟았다.

# 문제에서 이해한 것이 최대한 맞다고 생각을 하고 이해되지 않는 예제가 보이면 한 번 반례를 생각하고 아니면 다시 원래 대로 돌아오는게 맞는 것 같다.

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

flag = 0
def dfs(num,count,temp): 
    global flag
    if flag == 1:
        return
    if count == 4:
        flag = 1
        return
    for node in data[num]:
        if node not in temp:
            temp.append(node)
            dfs(node,count+1,temp)
            temp.pop()

for i in range(n):
    temp = list()
    temp.append(i)
    dfs(i,0,temp)
    if flag == 1:
        print(1)
        break
if flag == 0:
    print(0)

접근법

그래프 탐색을 할 때 보통 꼬리에 꼬리를 물고 있는 것을 구하라하면 dfs로 풀고, 같은 레벨이나 거리를 구하라하는 문제는 bfs로 푼다. 정하고 풀지는 않지만 생각하기 쉽게 틀을 만들어둔다. 

 

※ 주의

이런 문제를 풀 때는 항상 방문처리를 조심해줘야 한다. 현재 재귀상태가 끝났으면 방문을 풀어줘야하는 것이다. 예를 들면 노드가 5개 있고 요 상태라고 가정하자 [[4], [4], [1,3] ,[4, 2],  [0, 1, 3]] 0부터 시작했다 했을 때 0 -> 4 -> 3 -> 2 -> 1로 가야한다. 하지만 방문처리 한것을 다시 풀어주지 않으면 0 -> 4-> 1경우에 1에다가 방문처리를 해주면서 0 -> 4-> 3-> 2일 때 1이 이미 방문처리가 돼있기 때문에 갈 수가 없다.