[백준 #1260 파이썬] DFS BFS

 

1260번: DFS와 BFS

혼자서 아무것도 모르고 풀어보려다 많이 거꾸러졌던 문제

지금도 DFS BFS를 다시 기억하기 위해서 계속해서 다시 풀어보고 있는 문제다

풀어볼 때마다 여전히 새롭고 괴롭다 ㅎㅎ 그래도 재귀가 조금씩 더욱 익숙해지고 있는 느-낌!

 

그렇다면 한번 풀어보자

우선은 기본적으로 생각해야 할 것들을 생각해보자

정점의 개수 N, 간선의 개수 M, 탐색을 시작할 정점의 번호 V가 주어진다. 

이 문제를 처음 볼 때는 정점이 1로 시작해야 풀기 편한게 아닌가 라는 바보같은 생각을 했지만 어떤 숫자가 오든지 크게 상관은 없었다

 

여기서 생각해주어야 할 건 방문 상태!

내가 어떤 노드를 탐색했는 지, 안했는지를 체크할 수 있는 수단이 필요하다..

방문 상태를 고려하지 않고 풀려면 방문한 노드를 계속 찾아서 제거해주는 방법이 있을 것 같은데 많이 복잡할 것 같다.

그래서 일단 방문 상태를 나타내주는 노드까지 코드로 구현해보겠다.

 

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

여기서 n+1 개수로 방문 상태와 그래프를 만들어준 이유는 인덱스 0때문이다. 5번까지 있는 노드를 만들 때 0~4로 총 5개의 노드를 담을 수 있는 리스트를 만들 수도 있다. 하지만 이런 방법은 5번 노드를 찾기 위해 4번 인덱스를 탐색해야 하기 때문에 헷갈리기 그지 없다!

 

그래서 0번 인덱스를 빈 리스트로 받아주고 나머지 1~5번 까지 있는 리스트로 만들어 주는 것이다. 방문 노드도 마찬가지!

그런 다음 특이한 점이 a인덱스에 b값을 넣어주고 b값에 a를 넣어주고 있다. 이러한 작업을 하는 이유는 그래프가 서로 연결되어 있는 상태이기 때문이다. 우리는 1에서 2로 갈 지 2에서 1로 갈 지 모르는 상황이다. 그렇지만 양방향이라는 특성을 알고 있다. 그러므로 저렇게 서로 값을 집이넣어준다..!

(만약에 방향성이 있다면 다르게 생각해보아야 하긴 한다)

 

백준의 예제 입력 2를 기준으로 보면 그래프의 결과는 이러한 형태를 나타낸다.

 

 

기본 세팅을 마쳤으니 이제 dfs를 한번 살펴보자 (아직까지는 기본 세팅에 뭐가 빠졌는지 인지하지 못함)

dfs는 그래프, 시작값, 방문상태를 고려하도록 해당 인자들을 모두 받도록 하였다. (시작 노드만 받고 구현할 수도 있음!)

 

먼저 시작 노드를 방문하도록 하자, 그러면 그 값을 출력해야 하고 방문상태를 True로 만들어줘야 한다.

그런 결과를 보도록 하자.

 

def dfs(graph,v,visited):
    # 현재 노드 방문 처리
    visited[v] = True
    print(v, end = ' ')

그러면 시작노드가 3이었으니, 3인 인덱스를 살펴보면 3을 출력하고 4와 1이 있음을 알 수 있다. 이는 3이 현재 4와 1과 연결되어 있음을 알 수 있다. 그러면 탐색을 똑같이 진행하기 위해선 3인 인덱스에 있는 4의 값을 받았으니 4번 인덱스로 이동하여 방문상태를 확인하고  같은 과정을 반복하면 된다. 그러면 흐름은 다음과 같아진다.

def dfs(graph,v,visited):
    # 현재 노드 방문 처리
    visited[v] = True
    print(v, end = ' ')

    for i in graph[v]:
        if not visited[i]:
            dfs(graph,i,visited)

4번 인덱스를 방문했는 지 살펴보고, 방문하지 않았다면 다시 재귀로 depth를 깊이 파고 들어가는 것이다. (4출력)

그러면 4번 인덱스는 방문 처리되고, 5번 인덱스로 이동한다. (5 출력)

5에서는 4를 방문했으니 패스 2를 방문하지 않았으니 인덱스 2로 이동 (2 출력)

2에서는 5 방문했으니 패스, 인덱스 1 방문 (1 출력)

1에서는 인덱스 2방문했고 다시 3으로 이동했는데 3번 인덱스는 방문했다. 그러므로  depth에서 빠져 나온다.

그러면

1에서의 함수 종료 -> 2에서의 함수 종료 -> 5에서의 함수 종료 -> 4에서의 함수 종료 -> 3에서의 함수 종료

로 모든 함수가 종료되고 출력값은

3 -> 4 -> 5 -> 2 -> 1이다

 

출력예제의 정답은 3 1 2 5 4였는데 왜지??

 

정답은 정렬에 있다.

탐색 과정에서 오류가 있는 것은 없다.

 

하지만 문제를 보면 작은 것을 먼저 방문한다는 전제가 있다.! 그러니 문제를 똑바로 보자 나처럼 고생하지 말고 ㅎ

문제도 잘 보고, 입력해야 하는 값의 범위도 항상 고려해야 한다. 소수찾기 문제에서도 1인 상황에 대해서도 처리가 필요한데 이를 인지 못해서 틀려버리는 경우도 있다. 그러니 항상 문제를 잘 읽고 따로 처리가 필요한 부분이 있는지 살펴봐야 한다.

 

기본 조건을 변경해준 것과 dfs 결과로 중간 정리를 해보자

def dfs(graph,v,visited):
    # 현재 노드 방문 처리
    visited[v] = True
    print(v, end = ' ')

    for i in graph[v]:
        if not visited[i]:
            dfs(graph,i,visited)

n,m,v = map(int,input().split())
visited = [False]*(n+1)
graph = [[]for i in range(n+1)]
for _ in range(m):
    a,b = map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)
    
for i in range(len(graph)):
    graph[i].sort()

이제 bfs로 값을 내보자

bfs는 주로 queue를 활용한다. 파이썬에서는 이를 deque로 표현하고 있으니 이를 꼭 인지하자

queue의 특징은 개인적으로 찾아보시길! (선입선출 구조로 보면 쉬워요!)

 

우선 시작 노드로 큐를 만들어주자 그리고 그 노드는 방문 처리를 해주자

 

이제는 잘 정렬된 그래프로 보자

3을 큐에서 먼저 출력하고, 인덱스 3을 보면 [1,4]가 있다.(이쯤에서 bfs 특징 생각하기!!)

인덱스 1로 이동 인덱스 1을 방문하지 않았으므로 큐에 추가. 그리고 인덱스 1을 방문 처리 (큐 : [1])

그리고 인덱스 4 탐색(3 인접한 건 모두 확인) 인덱스 4 방하지 않았으므로  큐에 추가. 그리고 인덱스 4 방문처리 (큐 : [1,4])

 

그리고 이 과정을 반복하면 됩니다. 이제 코드로 볼까요?

rom collections import deque

def bfs(graph,v,visited):
    queue = deque([v])
    visited[v] = True

    while queue:
        k = queue.popleft()
        print(k, end = ' ')
        
        for i in graph[k]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True

 

이어서 흐름을 보면

1출력, 인덱스 1에 있는 [2,3]가 있다.

아까 설명한 과정을 반복 (3은 처음에 했으니 패스)

큐는 [4,2,5]가 되고 결과적으로 이 순서대로 출력된다.

 

그러면 bfs의 출력 순서는 3 1 4 2 5

 

그런데 문제는 dfs, bfs의 결과를 모두 요구하고 있다.

우리가 고려해줘야 할 것은 초기화

dfs에서 방문한 결과를 그대로 bfs에 적용할 수는 없으니 중간에 방문 현황을 초기화해주어야  한다. 문제를 풀면서 꼭 인지!

그렇게 해서 나온 최종 결과

from collections import deque

def dfs(graph,v,visited):
    # 현재 노드 방문 처리
    visited[v] = True
    print(v, end = ' ')

    for i in graph[v]:
        if not visited[i]:
            dfs(graph,i,visited)

def bfs(graph,v,visited):
    queue = deque([v])
    visited[v] = True

    while queue:
        k = queue.popleft()
        print(k, end = ' ')
        
        for i in graph[k]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True

n,m,v = map(int,input().split())
visited = [False]*(n+1)
graph = [[]for i in range(n+1)]
for _ in range(m):
    a,b = map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)
    
for i in range(len(graph)):
    graph[i].sort()

print(graph)


dfs(graph,v,visited)
visited=[False]*(n+1)
print()
bfs(graph,v,visited)

이러면 bfs dfs에 대 해서 어느정도 감을 잡을 수 있습니다. ㅎ 이를 기반으로 본격적으로 다른 문제들을 풀어보겠습니다..!