백준 1260번(DFS와BFS) 파이썬

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

1260번: DFS와 BFS

드디어 DFS와BFS에 대해 공부를 시작했다. 

정말 어렵다!!!!!!!!!!!!

이해를 하는데 상당한 시간이 걸렸다. 그래서 어쩔수없이 다른 사람들의 코드를 참고하였다.

이 유형들은 내가 이번 방학동안 꼭 정복하고 말것이다. 아래는 풀이 코드이다.

설명은 주석처리로 해놓았다.

 

from collections import deque

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

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

for _ in range (M):
    a,b =  map(int,input().split())
    graph[a][b] = True #서로 연결된부분은 
    graph[b][a] = True #둘다 True로 변형해준다
    
visited_dfs = [False]*(N+1) # 미방문 리스트를 만든다
visited_bfs = [False]*(N+1) # 범위가 N+1인 이유는 이해하기 쉽게 [0]이 첫번째가 아닌 [1]이 첫번째로 하기 위해서이다.

def dfs(V):
    visited_dfs[V] = True # 시작 노드를 방문처리 해준다
    print(V, end=" ") 
    for i in range(1,N+1):
        if (visited_dfs[i] == False and graph[V][i] == True): # 방문하지 않았으며 True 바뀐 노드와 인접한경우!
            dfs(i) # 재귀호출!
            
def bfs(V):
    q = deque([V]) #데크를 쓰는 이유는 출입구가 양쪽에 있기 때문에 빠른 데이터 처리가 가능하기 때문이다
    visited_bfs[V] = True # 시작 노드 방문처리
    while q: # q가 빌때까지
        V = q.popleft() #방문한 노드를 V에 대입
        print(V, end=" ") 
        for i in range(1,N+1): 
            if visited_bfs[i] == False and graph[V][i] == True: # 위의 DFS 설명과동일
                q.append(i) # 데크에 추가해준다
                visited_bfs[i] = True # 그리고 방문처리

dfs(V)
print()
bfs(V)

DFS는 "재귀함수"의 특징을 가지고

BFS는 "deque"를 사용하는 특징을 가진다. 

두 알고리즘의 차이점인거 같다.

난이도가 있는 알고리즘의 경우 무작정 들이박는거보단 사전에 공부를 하고 시작하는게 맞다고 생각한다.

개인적으로 무작정 들이박으면 시간낭비가 될 거 같다... 효율이 좋지 못하다는 얘기다!!

물론 경험담이다 ㅋㅋ....