백준 4803 : 트리 (Python)

본문 링크

import sys
input=sys.stdin.readline

def DFS(Previous,node):

    visit[node]=True #방문처리

    for i in Tree[node]:

        if i==Previous: #이전노드와 다음노드와 같다면 DFS를 수행하지않는다.
            continue
        if visit[i]: #만약 이미 방문한지점이라면 False 반환
            return False
        if not DFS(node,i): #다음노드와 이전노드가 다를 경우 DFS 실행.
            # DFS 탐색시 이미 방문한 지점에 도착할경우 사이클이 존재하기 때문에 False 반환
            return False
    return True # DFS 탐색후 사이클이 발생하지 않았으면 True 반환


time=0

while True:
    time+=1
    N,M=map(int,input().split())

    if [N,M]==[0,0]:
        break

    Tree=[ [] for _ in range(N+1) ] # 트리 그래프 생성

    for i in range(M):
        u,v=map(int,input().split())
        Tree[u].append(v) #양방향이기 떄문에 두번 원소 추가
        Tree[v].append(u)

    cnt=0 # 트리의 개수
    visit=[False]*(N+1) # 방문체크 배열 선언

    for i in range(1,N+1):
        if not visit[i]: #만약 방문하지 않은 지점이라면
            if DFS(0,i): #DFS 수행결과시 True 일경우 cnt+1
                cnt+=1
    if cnt == 0:
        print("Case {}: No trees.".format(time))
    elif cnt == 1:
        print("Case {}: There is one tree.".format(time))
    else:
        print("Case {}: A forest of {} trees.".format(time, cnt))

📌 어떻게 접근할 것인가?

그래프가 주어졌을때 트리인지 아닌지 판별하는 문제입니다.

이 문제를 풀면서 return 에 대해 좀 더 깊게 공부했습니다.

📌 첫번째 조건문 , if i==Previous

첫번째 조건문입니다. 왜 이런조건 사용했을까요?
일단 의미는 "이전 노드와 현재 노드가 같은가?" 입니다.

먼저 저희는 트리를 입력받을때 양방향이기 때문에 두번 입력받았습니다.

• Tree[u].append(v) #양방향이기 떄문에 두번 원소 추가
  Tree[v].append(u)

하지만 만약에 1,2 를 입력받았다고 가정해봅시다.

Tree[1]=2 , Tree[2]=1 트리는 이런형태로 만들어집니다.
이제 1을 먼저 탐색해보겠습니다. 그러면 2로 갑니다. 이때 1은 visit 배열을 통해 방문처리를 해줍니다. 이제 다시 Tree[2] 값은 1이 됩니다.

만약 if i==Previous 를 사용하지 않았다면 1은 이미 방문처리 한 지점이기 때문에

두번째 조건문

• if visit[i]: return False #만약 이미 방문한지점이라면 False 반환

으로 인해 $False$ 가 나오게 됩니다. 따라서 첫번째 if문은 필요합니다.

📌 3번째 조건문 , if not DFS(node,i)

제가 처음에 짠 코드는 아래와 같습니다.

if visit[i]: #만약 이미 방문한지점이라면 False 반환
	return False
else:
	DFS(node,i)

하지만 제대로 된 코드는 아래와 같습니다.

if visit[i]: #만약 이미 방문한지점이라면 False 반환
	return False
if not DFS(node,i): 
    return False

무슨 차이일까요?

else 문을 통해 $DFS$ 를 탐색하게 되면 트리이기 때문에 여러 분기로 나뉘게 됩니다.
그렇다면 재귀호출된 $DFS$ 마다 $return$ 값이 달라질 수 있습니다.

즉 어떤 $DFS$ 가 끝까지 탐색해서 $True$ 의 값을 반환할지라도 또다른 $DFS$ 에서는 $False$ 를 반환 할 수 있기에 정확한 판별이 되지 않습니다. 따라서 else 문으로 $DFS$ 탐색시 return False 값이 버려질수 있습니다.

시험에서 100점을 얻기 위해서는 모든 문제를 맞춰야 하므로 모든 문제를 확인해야합니다.

따라서 2번째 if 문 처럼 if not DFS(node,i) 를 해주면 $DFS$ 를 실행하고 $return$ 값 또한 확인이 가능합니다.

예시로 이런 입력이 주어졌을때

• 1 2
  1 3

2번에서 $True$ 가 나오면 1 로 올라오고 $True$ 가 반환이 되는데 이럴때는 3번이 탐색이 안되어있습니다. 마지막에 return True 을 만나버려 함수가 종료되어 탐색을 다 못하기 때문이죠.

따라서 $True$는 끝까지 돌면서 반환을 시켜서는 안되므로 두번째 코드에서는 모든 DFS(node,i) 에 대해 한번이라도 $False$ 값이 나오면 return False 를 해주는겁니다.

첫번째 코드처럼 else 문을 사용해서 DFS(node,i) 를 사용하면
$False$ 값을 반환하기 전에 함수가 종료될 수 있습니다.