[DFS/BFS]백준_1260_DFS와 BFS(이론 정리)

• 알고리즘 유형 : 그래프 - DFS/BFS, 재귀
• 풀이 참고 : 동기의 가르침
• 문제 링크 : https://www.acmicpc.net/problem/1260

늘 언급하지만 해당 내용은 정확하지 않아 개발 공부에 도움이 되지 않습니다. 

그래서 당연히 귀한 시간 내주시어 지적해 주시면 감사 드리겠습니다. 

---

DFS와  BFS 정리

1. 왜 하는가

  - 그래프를 탐색 하는 용도이다.

  - 해당 예제는 노드의 개수와 노드 값이 주어지고 연결된 인접 노드까지 주어 진다.

  

2. 어디에 쓰는가

  - 모든 노드(데이터)를 확인 하는 용도로 주로 사용한다.

  - 각 노드의 특징들을 체크하는 용도로도 좋다고 한다. 

  - 데이터간의 최단거리를 구하는 용도로 사용한다. 

---

풀이 요약

중요한 점들로 정리해보겠다. 

1. 어떤 노드를 체크했는지 확인하는 용도의 visited

  - 이전까지 나에겐 사용하기 너무 어려운 방법이라 피했지만 이제 못 피할 거 같다. 많이 써보자

# dfs 확인여부 체크용 visited
visited1 = [0] * (n+1) # 지나갔던 노드를 체크하기 위한 리스트
# bfs 확인여부 체크용 visited
visited2 = [0] * (n+1)

2. 주어진 인접노드 받기(중요)

  - 리스트로 받는 방법과 행렬로 받는 방법이 있으나 난 행렬 울렁증이 있어 리스트로 받았다. 

  1) 2중 빈리스트를 만든다.

  2) 1번에서 중요한 부분은 노드의 개수보다 하나 더 받는다는 것!

    - 이유는 나중에 재귀를 돌리고 반복문돌리면서 체크를 해야 하는데, 편하게 하기 위해서(처음 생각 한 사람 천재다)

  3) for문으로 문제에 주어진 값을 받아 리스트에 넣는다.

  4) 요기서 보면 append할때 노드별로 인접 노드들을 같이 넣어주는 코드가 있있다.(처음 생각 한 사람 천재다)

tree = [[] * (n+1) for _ in range(n+1)] # 노드별 인접 경로를 2차원으로 받기위한 2중리스트, 인덱스0은 추후 작업 편의상 비어둠 
for _ in range(m): # 만들어 둔 2중 리스트에 노드별 인접 경로를 리스트로 받음
    a, b = map(int, input().split())
    tree[a].append(b)
    tree[b].append(a)

3. DFS(재귀)

  1) 방문한 노드를 visited의 해당 인덱스로 체크하여 방문체크(난 노드 값으로 체크함)

  2) for 문으로 방문한 노드의 인접 노드들 중 방문하지 않은 노드가 있다면 거기로 재귀 시작

 

4. BFS(큐)

  1) 방문한 노드를 인큐

  2) 큐에 넣으면서 visited에 방문체크(이것 역시 노드 값으로 그냥 넣음)

  3) while문을 돌면서 디큐를 한 후 디큐한 값으로 인접 노드의 방문 여부를 확인

  4) 확인 후 체크했던 노드가 아니면 1,2번 반복

 

코드에 더 자세히 설명 함

---

코드(python)

import sys
from collections import deque
# 04. https://www.acmicpc.net/problem/1260 : DFS 와 BFS
input = sys.stdin.readline
# n: 노드 개수, m: 엣지 개수, v: 시작 정점 key값
n, m, v = map(int, input().split())

# dfs 확인여부 체크용 visited
visited1 = [0] * (n+1) # 지나갔던 노드를 체크하기 위한 리스트

tree = [[] * (n+1) for _ in range(n+1)] # 노드별 인접 경로를 2차원으로 받기위한 2중리스트, 인덱스0은 추후 작업 편의상 비어둠 
for _ in range(m): # 만들어 둔 2중 리스트에 노드별 인접 경로를 리스트로 받음
    a, b = map(int, input().split())
    tree[a].append(b)
    tree[b].append(a)

for i in tree: # 인접 노드들을 오름차순으로 sort
    i.sort()

def dfs(start_node):
    visited1[start_node] = start_node # 처음 시작 하는 노드 체크, 이후재귀에서는 Tree의 노드별 연결 노드를 찍어 줄꺼임
    print(start_node, end = ' ') # 아래 반복문에서 재귀로 넘어온 tree의 노드를 프린트 

    for i in tree[start_node]: # 노드별 연결된 노드를 하나씩 확인 
        if i != visited1[i]: # 노드와 vistited1의 노드값과 같지 않다면
            dfs(i) # 다시 재귀
        else:
            continue # 아니면 반복문 다시!

# bfs 확인여부 체크용 visited
visited2 = [0] * (n+1)
# bfs 확인 용 큐
queue = deque([])

def bfs(start_node):
    print(start_node, end=' ') # 처음 시작 노드 찍고 시작
    visited2[start_node] = start_node # 함수 인자로 들어온 노드를 지나갔으니 visited 인덱스에 찍고
    queue.append(start_node) # 인큐
    
    while queue:
        check = queue.popleft() # 디큐 후 확인 들어감
        for i in tree[check]: # 디큐한 노드의 인접 노드들을 하나씩 확인 할꺼임
            if i != visited2[i]: # 인접 노드가 체크했던 노드가 아니면 반복문 돌리기
                visited2[i] = i # 체크 안했던것들을 경로에 체크하고 인큐
                queue.append(i)
                print(visited2[i], end=' ') # 답을 위해 프린트도 찍어줌
            else:
                continue # 방문 했던 노드일 경우 다시 반복문 

dfs(v)
print()
bfs(v)

---

배운 점, 배울 점

1. DFS, BFS의 개념은 많이 이해했다.

2. visited 체크방법을 많이 배웠다.

3. 재귀 공부를 계속 지속해야 한다.

4. 코드잇으로 개념 잡기 좋다.

5. 다른 문제들에 적용해보자