DFS/BFS 그래프 이론 공부

정점의 개수와 간선의 개수가 주어진다. 그 다음으로 탐색을 시작할 번호 V가 주어진다. 방문 가능한 정점이 여러 개면 번호가 작은 것을 먼저 방문하고, 더 이상 방문 가능한 점이 없으면 종료한다. 정점번호는 1번부터 N번까지이다.

간선의 개수와 시작 정점이 주어짐
그럼 연결리스트 써야 되나?

간선간의 연결을 어떻게 표현할 것인가
12 13 14 24 34
1 - 234
2 - 14
3 - 14
4 - 13
연결 리스트
인덱스로 앞 원소 주면 받아서 작은 수부터 탐색 방문한 점을 찍어야 하니까
DFS로 가면 가장 가까운 노드 찾아감

우선 하나씩 생각
DFS로 간다.
시작 노드 가서 연결리스트 가장 작은거부터 봄 (오름차순이니까 순서대로 간다 치고)
그 작은거 간거에서 이어진거 봄 이어진거 있으면 가장 작은거 방문
더이상 없으면 부모 노드로 올라와서 있는지 확인
2 아래의 모든 노드 탐색시 종료

BFS
시작노드가서 연결리스트부터 다 방문함
그 다음 연결리스트의 자식노드 순서대로 방문함(?)
헷갈리네

---

아예 구현의 개념도 못 잡으니 문제유형에 익숙해지기
(DP면 DP테이블 만들어서 점화식 세우는 것처럼)

보통 DFS는 스택으로, BFS는 큐로 구현함

DFS 스택 구현
1. 탐색 시작 노드를 스택에 넣어 방문처리
2. 최상단 노드에 미방문 인접노드가 있다면 스택에 넣어 방문처리, 없으면 pop. (스택 = 방문)
3. 2가 더 이상 수행 불가할 때까지 반복.

-> 재귀로 구현한다는 건 알겠는데 스택이 필요한지 이해 부족

BFS 큐 구현
1. 탐색 시작 노드를 큐에 삽입한다.
2. 큐에 가장 맨 앞 노드를 뽑아서 인접노드를 모두 큐에 넣는다. (방문처리)
3. 2가 더이상 수행될 수 없을 때까지 반복한다.

-> 아 큐를 하나씩 뽑아서 출력하고 방문할 수 있으면 그때 visited를 True로 만들고 q에 넣는구나!

그래프는 어떻게 주냐? >> 2차원 리스트로 생각하면 편하다.
이차원 리스트에서 [a][b]가 1이면 연결되어 있다고 생각하고 만든다.
(동적할당의 연결리스트는 다른 문제에서 알아보자)

BFS DFS 문제를 풀 때는 웬만하면 visited 배열이 반드시 필요하다.
노드의 방문 여부를 판단하는 노드의 visited = [False] * 노드 수
(방문했는지 검사용이다.)
더 이상 갈 수 없다 = 모든 visited가 true임

근데 다음 노드도 다 확인해봐야 하는데 3번 4번도 모두 확인해보고 종료가 되는 것이다.

큐에 1 > 2 3 4 > 3 4 > 4 > end 1 2 3 4

---

입출력이 많으면 연결리스트로, 적으면 어레이 리스트를 사용하는 것이 좋다.

연습코드 백준 1260번 DFS BFS
익숙해지려면 다른 문제 더 풀어봐야겠다

'''
DFS/BFS
'''
import sys


def dfs(idx):
    global visited
    visited[idx] = True
    print(idx, end=' ')

    for next in range(1, N+1):
        if not visited[next] and graph[idx][next]:  # 방문할 수 있어
            dfs(next)  # 재귀로 한거야


def bfs():
    global q, visited
    while q:  # 큐가 남아 있을 때까지
        cur = q.pop(0)
        visited[cur] = True
        print(cur, end=' ')
        for next in range(1, N+1):
            if not visited[next] and graph[cur][next]:
                visited[next] = True
                q.append(next)


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

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

# 간선정보 입력
for _ in range(M):
    a, b = map(int, input().split())
    graph[a][b] = True
    graph[b][a] = True

dfs(V)
print()

visited = [False] * (N+1)
q = [V]
bfs()
 입력하세요