DFS BFS 내맘대로 풀어보기 (BOJ 1260)

https://www.acmicpc.net/problem/1260

1260번: DFS와 BFS

DFS 깊이 우선 탐색

왜 쓰는가?

모든 노드를 방문해야 하는 경우에. (방문 노드를 저장해서 다시 가지 않기 때문)

길 찾기. 미로 문제

사이클의 존재 여부를 확인할 때 

 

Depth -> 그냥 deep이라고 외움. 딥하게 들어가는 느낌

어떻게 구현하나?

주로 재귀와 stack을 이용한다

재귀는 간단한데 시간복잡도가 큰 듯하다. (지금까지 풀었을 때의 생각)

 

시작에서 최대한 깊게 탐색 -> 끝나면 뒤로 돌아가 다른 경로 이용

하나의 방향을 결정하면 그 방향을 따라 끝까지 도달한다

끝이면 이전 단계로 돌아감

 

BFS 너비 우선 탐색

형제 노드

시작 노드의 인접한 노드를 모두 탐색한 다음 다음 노드 이동

방문한 노드를 저장 -> 먼저 저장된 노드부터 출력

큐를 이용

 

** 

스택과 큐의 차이는 무엇인가

스택은 쌓아 올리는 것

Last in first out  --> 가장 위인 top만 건드리기 가능

가장 마지막에 삽입된 자료가 가장 먼저 삭제

push해서 넣고

pop해서 나온다. 

** pop() -->return의 의미도 들어가 있음

그냥 list의 append(), pop()

append() 맨 뒤에 값 삽입

pop() 맨 뒤의 요소 삭제, 반환

 

큐는 줄 서서 기다리는 것

먼저 온 사람일수록 먼저 처리한다. 마치 음식점처럼

큐는 한쪽 끝에서(front) 삭제

반대편에서(rear) 삽입한다

그니까 굴러온 돌이 박힌 돌 뺀다

 

from collections import deque

이 모듈을 사용해서 많이 구현함

queue.popleft() --> 사용시 첫 번째 데이터를 제거

queue.appendleft() --> 데이터를 맨 앞에서 삽입

 

시간 복잡도

데이터 추가/삭제는 O(1), 데이터 접근은 O(N)

 

---

슈도 코드

DFS

일단 현재의 형태는 간선 기준으로 작성되어 있으므로 한 노드에 어떤 노드가 연결되어 있는지 모른다

그래서 그래프 형태를 바꿔준다 / 인접행렬로

n, m, v = map(int, input().split())
arr = [[] for _ in range(n+1)]
for i in range(n+1):
    a, b = map(int, input().split())
    arr[a].append(b)
    arr[b].append(a)

 

결과는 아래와 같이 나옴

[[], [2, 3, 4], [1, 4], [1, 4], [1, 2, 3]]

 

이 상태에서 dfs의 개념을 생각해본다

일단 우리는 시작점을 알고 있다

그리고 시작점인 1 -> 연결된 2로 가야 한다 -> 2와 연결된 4로 가야 한다 -> 4에서 멈춘다

다시 남은 3으로 간다. 

1 - 2 -4 -3

다른 예제에서도 보자

5 5 3
5 4
5 2
1 2
3 4
3 1
[[], [2, 3], [5, 1], [4, 1], [5, 3], [4, 2]]

아 sorting을 해야겠다

[[], [2, 3], [1, 5], [1, 4], [3, 5], [2, 4]]

3 -> 1->2 ->5 ->4

 

특징은

방문한 곳은 다시 가지 않는다 => 방문한 곳을 순서대로 저장할 곳이 필요하다

내가 방금 방문한 곳을 x 라고 했을 때

arr[x] 에서, 방문한 곳을 제외한 나머지 노드를 순서대로(오름차순) 방문해야 한다

 

이제 나는 스택이나 재귀를 이용해야 한다는 것을 알고 있다

그러나 재귀는 일단 차치하고, 스택을 이용하려면 어떻게 해야 할까 

 

스택의 특징은 가장 마지막에 넣은 것을 가장 먼저 뺀다는 것이다

우리에게 중요한 것은 방문 순서. 방문 순서는 채워야 하지 빼는 것이 아님

근데 스택이 왜 필요할까. 가장 먼저 뺀다는 특징을 걍 잊어버려야 하는건가

 

---

a = [1,2,3]

b= []

b.append(a.pop())

a=[1,2]

b=[3]

--

 과외 받고 왔다

재귀로 생각해본다

 

1. 맨 처음 방문하는 노드는 정해져 있다

2. 방문 여부를 파악하기 위해 방문 함수를 arr[]와 비슷한 구조로 만든다

그니까 visit=[] 그 노드의 위치와 visit[i]의 값이 맞도록 세팅하여 바로바로 얘가 방문이력이 있는지 없는지 파악하는 것이다

 3. 그래서 만약 내가 1에 방문하면 -> arr[i]에 있는 애들을 탐색한다

그리고 거기 있는 애가 방문 이력이 없다? -> 다시 dfs 돌려서 방문 여부 업데이트 + 걔와 연결된 노드에 대한 탐색을 수행한다

 

def dfs(arr, v, visited):
    visited[v]=1
    print(v, end=' ')

    for i in arr[v]:
        if visited[i] == 0:
            #방문한 적 없음
            dfs(arr, i, visited)
            
    
n, m, v = map(int, input().split())
arr = [[] for _ in range(n+1)]
for i in range(m):
    a, b = map(int, input().split())
    arr[a].append(b)
    arr[b].append(a)
    arr[a].sort()
    arr[b].sort()

visited = [0]*(n+1)

print(dfs(arr, v, visited))

** 왜 None이 나오는가

v는 내가 지금 방문한 노드임

그러니까 탐색을 하려는 노드

그래서 v의 값을 나열한 것이 (방문한 노드는 다시 방문하지 않으므로) 탐색 순서가 되는 것

예제1에서 v는 1 2 4 3 None 이 나온다. 

어쨌든 이 None은 dfs라는 함수의 값이므로 다시 생각해보면..

그니까 결국 나는 v를 print하는 거니까

v=3 --> print(3) 하고 for문 돌렸는데 

for i in arr(3):

if visited(i) == 0:

dfs(arr, i, visited) 인데..

여기서 if 조건에 해당하지 않으면 종료 아닌가?

 생각해보니 종료구문을 안쓴거같음

 

--

정답을 들었는데 종료구문은 아니고

나중에 마저 쓰겠다