[백준/24479/파이썬(Python)] DFS, 알고리즘수업-깊이우선탐색1

[백준/24479/파이썬(Python)] DFS, 알고리즘수업-깊이우선탐색1

24479번: 알고리즘 수업 - 깊이 우선 탐색 1 (acmicpc.net)

 

코드

1. pypy

from sys import stdin,setrecursionlimit


#결과 리스트
result = [0]
#입력
N, M, R = map(int, stdin.readline().split())

#방문여부 정점(노드)
visited = [False] * (N+1) #0번째도 Flase로 했기 때문


graph = [[]for i in range(N+1)] #2차원만 컴프리핸션 써야함 다 복사돼서
setrecursionlimit(N+10)
for i in range(M):
    #ex) u번노드에 v연결됨
    u, v = map(int, stdin.readline().split()) #연결된 노드(정점)을 입력받는다. 
    graph[u].append(v) #1번째 2
    graph[v].append(u) #2번째 1 추가
# print(graph)

def dfs(graph, visited, t): #그래프, 방문보기, 시작노드
    visited[t] = True #방문처리
    result.append(t) # 결과 리스트
    
    for i in graph[t]: #graph[t]번째
        if visited[i] == False : #방문하지 않았다면, 그 노드를 방문처리
            dfs(graph, visited, i )


for j in range(N+1): # 오름차순 정렬
    graph[j]=sorted(graph[j])

dfs(graph, visited, R)

# 시작 정점에서 방문할 수 없는 경우 0 출력
# visited[i]번째가 false이면 0 출력
for i in range(1, N+1): #1부터 N까지
    if visited[i] == False:
        print(0)
    else:
        print(result.index(i))
        # pass

 

 

2. 파이썬 Python

from sys import stdin,setrecursionlimit

def hingguri():
    #결과 리스트
    result = [0]
    #입력
    N, M, R = map(int, stdin.readline().split())

    #방문여부 정점(노드)
    visited = [False] * (N+1) #0번째도 Flase로 했기 때문


    graph = [[]for i in range(N+1)] #2차원만 컴프리핸션 써야함 다 복사돼서
    setrecursionlimit(N+10) # 깊이를 늘림, 트리 층 늘린다. -> 런타임 에러 해결
    for i in range(M): #i를 쓰지 않으면 _로 하면 됨
        #ex) u번노드에 v연결됨
        u, v = map(int, stdin.readline().split()) #연결된 노드(정점)을 입력받는다. 
        graph[u].append(v) #1번째 2
        graph[v].append(u) #2번째 1 추가
    # print(graph)

    count = 1
    def dfs(graph, visited, t): #그래프, 방문보기, 시작노드
        nonlocal count
        visited[t] = count #방문처리
        # result.append(t) # 결과 리스트
        
        for i in graph[t]: #graph[t]번째
            if visited[i] == False : #방문하지 않았다면, 그 노드를 방문처리
                count +=1
                dfs(graph, visited, i )


    for j in range(N+1): # 오름차순 정렬
        graph[j]=sorted(graph[j])

    dfs(graph, visited, R)

    for i in range(1, N+1):
        if visited[i] != False:
            print(visited[i])
        else:
            print(0)


# 시작 정점에서 방문할 수 없는 경우 0 출력
# visited[i]번째가 false이면 0 출력
# for i in range(1, N+1): #1부터 N까지
#     if visited[i] == False:
#         print(0)
#     else:
#         print(result.index(i))
        # pass
hingguri()

---

풀이는 내일 해야겠다.

쉽지않다... 

파이파이는 결국 풀었는데 파이썬은 계속 시간초과가 나와서 정답을 참고했다.

global이랑, nonlocal이라는 키워드를 알게됐다. 내일 다시 풀어보고 코드를 정리해서 다시 올려야겠다.

setrecursionlimit()함수를 이용해서 런타임에러를 해결했다. 이 함수는 재귀의 깊이를 늘려주는 것이다. (트리의 층을 늘려줌)

-> RecursionError가 재귀함수로 인해 발생하는 것이기 때문이다.

---

런타임에러 계속 나와서 스트레스 엄청 받음..