DFS와 BFS - 특정 점에서 모든 경로를 찾을 때

 

백준 1260번을 기준으로 풀어보겠다 

from collections import deque

import sys

N,M,V = map(int,sys.stdin.readline().split())

graph = [[0]*(N+1) for _ in range(N+1)]

for i in range(M) :

    x, y= map(int,sys.stdin.readline().split())

    graph[x][y] = 1

    graph[y][x] = 1

공통으로써, 1~5이지만 편의를 위해 0부터 GRAPH의 연결을 표시했다.

그 이후, 각 노드간의 연결점을 그래프로 표현하였다.

 

visited = [True] * (N+1)

지나감을 알려주는 방법, 1차원 배열을 이런식으로 표현할 수 있음에 주의하자 

DFS

 준비 사항 : 

 1. 그래프간의 연결을 알려줄 표 

 2. 노드가 지나감을 알려줄 표 

 3. 재귀함수 

  3 - 1 재귀함수는 출발점을 색칠한다 

  3 - 2 출발점이 색칠되지 않았고, 연결되어 있다면 다음 곳으로 넘어간다 .

 

for i in range(M) :

    x, y= map(int,sys.stdin.readline().split())

    graph[x][y] = 1

    graph[y][x] = 1

visitedfs = [False] * (N+1)

visitedbfs= [False] * (N+1)

def dfs(node) :

   

    visitedfs[node] = True

    print(node,end=" ")

    for i in range(1,N+1) :

        if not visitedfs[i] and graph[node][i] == 1 :

            dfs(i)

 

BFS 

 

준비 사항 :

 1. 그래프간의 연결을 알려줄 표 

 2. 노드가 지나감을 알려줄 표 

 3. 일반 함수 

 4. 일반 함수에서 지나간 곳을 저장할 queue 

*여기가 헷갈렸는데, 함수상으로 deque([node])만 해도 지속적으로 append 된다. 

    q = deque([node])

5. queue에서 popleft를 하여, 해당 node와 연결된 모든 곳을 색칠 

6. queue 순으로 반복 

 

def bfs(node) :

    q = deque([node])

    visitedbfs[node] = True

    while q :

        x = q.popleft()

        print(x,end =" ")

        for i in range(1,N+1) :

            if (visitedbfs[i] == False) and graph[x][i] == 1 :

                q.append(i)

                visitedbfs[i] = True

 

 

백준 24479 

혼자서 풀고.. 해냈다 생각했는데 메모리 초과가 나왔다. ㅠ 

import sys

N,M,V = map(int,sys.stdin.readline().split())

graph= [[0]* (N+1) for _ in range(N+1)]

for i in range(M) :

    x,y = map(int,sys.stdin.readline().split())

    graph[x][y] = 1

    graph[y][x] = 1

visited = [False] * (N+1)

sequence = {}

for i in range(1,N+1) :

    sequence[i] = 0

def dfs (node,cnt) :

    visited[node] = True

    sequence[node] = cnt

    for i in range(1,N+1) :

        if (visited[i] == False) and graph[node][i] == 1 :

            dfs(i,cnt+1)

dfs(V,1)

print(sequence)

-내가 작성한 코드 

 

메모리 초과란 , 재귀함수가 너무 깊게 내려갔을떄 주로 발생

sys.setrecursionlimit(10**5)

이를 통해 깊이를 제한. 

 

cnt = 1

def dfs (node) :

    global cnt

    visited[node] = cnt

방문 했는지가 아니라 몇번 방문했는지로 확인할 수도 있다. 

 

    graph[x].append(y)

    graph[y].append(x)

graph의 연결 점의 크기를 줄일 수도 있다. 

- 이 형태를 , 인접 리스트라고 한다. 

 

그래도 안되어서.. 이 코드를 찾아 썼따

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

N, M, R = map(int, input().split())
graph = [[] for _ in range(N+1)]
path = []
result = [0]*(N+1)
visited = [-1]*(N+1)

for _ in range(M):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

for i in range(1, len(graph)):
    graph[i].sort()

def DFS(start):
    visited[start] = 1
    path.append(start)
    
    for adj_node in graph[start]:
        if visited[adj_node] == -1:
            DFS(adj_node)
    
    return

DFS(R)

for idx, node in zip(range(1, len(path)+1), path):
    result[node] = idx
    
print(*result[1:], sep="\n")

 

어떤점이 차이가 났는지는, 차후에 물어봐서 알아내도록 해야겠다.