[실버 II] 1260번. DFS와 BFS

 문제 

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

1260번: DFS와 BFS

 사용 언어 

Python3

 풀이 과정 

비슷한 로직으로 첫 번째 시도는 틀렸지만 두 번째에 뜬 맞았습니다!

DFS랑 BFS 개념을 여러번 공부중인데 그래도 문제에 적용하는게 왜 어려운지 나는....

공부 방법을 바꿔서 더 많은 문제의 예시를 좀 따라 쓰고 안 보고 다시 쳐보는 연습을 해야겠다.

 제출 답안 

# 입력 변수 받기
N, M, V = map(int, input().split())

# 인접 영행렬 생성
matrix=[[0] * (N + 1) for i in range(N + 1)]

# 방문한 곳 체크를 위한 배열 선언
visited = [0] * (N + 1)

# 입력 받는 두 값에 대해 영행렬에 1 삽입
for i in range(M):
    a, b = map(int, input().split())
    matrix[a][b] = matrix[b][a] = 1


def dfs(V):
    # 방문한 곳은 1 넣기
    visited[V] = 1
    
    print(V, end=' ')
    
    # 재귀 함수 선언(V와 인접한 곳을 찾고 방문하지 않았다면 함수 실행)
    for i in range(1,N+1):
        if(visited[i]==0 and matrix[V][i]==1):
            dfs(i)

            
def bfs(V):
    # 방문해야 할 곳을 순서대로 넣을 큐
    queue = [V]
    
    # dfs 를 완료한 visited 배열(1로 되어있음)에서 0으로 방문체크
    visited[V] = 0
    
    # 큐 안에 데이터가 없을 때 까지
    while queue:
        V = queue.pop(0)
        print(V, end=' ')
        for i in range(1, N + 1):
            if(visited[i] == 1 and matrix[V][i] == 1):
                queue.append(i)
                visited[i] = 0

dfs(V)
print()
bfs(V)

 공부한 내용 

DFS와 BFS

몇 개의 문제를 이전에 풀어봤지만, 다시 개념부터 공부했다.

DFS

• DFS는 뒤에서 살펴볼 BFS와 같이, 맹목적으로 각 노드를 탐색할 때 사용한다.
• BFS는 큐를 사용하지만, DFS는 스택을 사용한다.
  여기서, 컴퓨터는 구조적으로 항상 스택의 원리를 사용하기 때문에(스택 프레임), 따로 스택을 사용하지 않고 재귀로도 구현이 가능하다. 재귀가 스택의 자료구조 원리를 사용하기 때문에 가능한 일이다. 보통 DFS는 재귀로 구현하는 경우가 많다.
• 트리순회(전위순회, 중위순회, 후위순회-루트노드의 위치에 따라 이름이 붙혀짐)는 모두 DFS의 한 종류이다.
  여기서 트리순회란, 트리구조에서 각각의 노드를 정확히 한번만, 체계적인 방법으로 방문하는 과정이다.
• DFS는 모든 노드를 방문해야할 때 사용한다.
• BFS보다 구현은 간단하지만, 느리다.

BFS

• 탐색을 할 때 너비를 우선으로 탐색한다. 즉 가까운 것 위주로 탐색한다. 이러한 특징때문에, '최단경로'를 찾는 문제에서 주로 사용된다.(ex. 미로찾기)
• 큐를 사용한다(FIFO)
• DFS와 같이, 맹목적인 탐색을 할 때 사용된다. (그래프, 트리 내 모든 노드를 방문하고 싶을 때, 찾는것을 발견할 때까지 모든 노드를 적어도 한번은 방문하고 싶을 때 사용한다.)
• 레벨순회(깊이가 1인노드>2>3... 더이상 방문할 곳 없으면 탐색 마침)

 

출처: https://velog.io/@rladpwl0512/8-DFS-BFS%EC%9D%98-%EA%B0%9C%EB%85%90