[백준/Python] 25195번(DFS)_Yes or yes

📌문제 유형

DFS (골드 Lv.4)

 

📌문제

25195번: Yes or yes

 

📌나의 문제풀이

- 24%에서 시간 초과

## 입력 ##
import sys
sys.setrecursionlimit(10**6)

n,m = map(int,input().split())

maps = [[] for _ in range(n+1)]
for _ in range(m):
    u,v = map(int,input().split())
    maps[u].append(v)

s = int(input())
fans = list(map(int,input().split()))

## 출력 ##
def dfs(x,visited):
    global flag
    
    if x in fans:
        return

    # leaf node인 경우
    if maps[x] == []:
            flag = 1
            return
    
    for next in maps[x]:
        if maps[next] != []:
            dfs(next,visited+[next])
        elif maps[next] == [] and next not in fans:
            flag = 1
            return


visited = []
visited.append(1)
flag = 0
dfs(1,visited)

if flag == 1:
    print('yes')
else:
    print('Yes')

 

📌다른사람의 문제풀이

- Java 문제풀이 Python으로 변경해서 풀이 완료

[DFS] 백준 - 25195번: Yes or yes Java 풀이

import sys
sys.setrecursionlimit(10**6)

n, m = map(int,input().split())

maps = [[] for _ in range(n+1)]
for _ in range(m):
    u,v = map(int,input().split())
    maps[u].append(v)

S = int(input())
fans = list(map(int,input().split()))

def dfs(start):
    global tour

    if start in fans:
        return
    
    # 시작 노드에서 간선이 없을 때
    if maps[start] == []:
        tour = True
        return

    for i in maps[start]:
        if maps[i] != []:
            dfs(i)
        elif maps[i] == [] and i not in fans:
            tour = True

tour = False
dfs(1)

if tour == True:
    print('yes')    # 팬클럽 만나지 않고 이동 가능
else:
    print('Yes')

 

📌리뷰

- visited를 dfs 함수에 넣는것이 시간초과의 요소 -> True, False로 판단해서 시간복잡도 줄이기

- dfs에서 return은 함수가 끝나는 것이 아닌, leaf node 위로 갈 수 있게 하는 것

- 다른사람의 풀이에서 maps[i] != [] 와 maps[i] == []로 구분되어 있음에 주의