[백준] DFS와BFS (1260번, Java)

 

문제설명

입력 & 출력

 

나의 풀이

 

이번 문제는 DFS와 BFS를 활용하여 주어진 정점 V로부터 탐색하는 정점을 출력하는 문제입니다.

 

DFS와 BFS에 대한 개념이 있으시다면 어렵지 않게 풀 수 있는 문제였습니다.

 

 

먼저 가독성을 위해서 전역변수로 사용할 수 있는 변수들은 전역변수로 선언해 줍니다.

 

 

main문 먼저 설명하자면, 빠른 입력을 위해서 BufferedReader클래스를 사용하여 입력을 받아주고, StringTokenizer를 사용하여 간선이 연결하는 두 정점의 번호를 공백을 기준으로 분리를 해줍니다.

 

그리고 입력받은 정점의 크기만큼 정점을 나타내는 graph배열을 초기화해 줍니다. 이때 문제에서 나왔듯이 정점은 1부터 시작하기 때문에 "+1"을 해줘야 합니다.

 

그리고 간선의 개수 M만큼 반복하는 반복문에서 입력받은 정보들을 사용하여 두 정점을 연결해 줍니다.

 

75번째 줄에서 정점의 크기만큼 방문 여부를 체크할 visited배열을 초기화해 줍니다. 이전에 graph배열을 초기화할 때 같이 하지 않은 이유는 dfs를 탐색하고 난 뒤 visited배열에는 dfs의 정보가 남아있기 때문에 다시 초기화가 필요하기 때문입니다. 

 

따라서 dfs와 bfs를 호출하기 전에 visited배열을 초기화를 해줘야 합니다.

 

 

DFS함수에서는 주석으로 거의 다 설명이 가능할 것 같습니다.

 

먼저 인자로 받은 현재 정점을 방문처리해 주고, 방문한 정점은 출력을 해줍니다.

 

그리고 전체 정점을 순회하는 데 이때 문제에서 말했듯이 "정점은 1부터 시작"하기 때문에 반복문의 시작은 1이어야 합니다.

 

입력받은 정점 node와 연결된 정점이면서 아직 방문하지 않은 정점에 대해서 dfs를 재귀적으로 호출하면 깊이 우선 탐색으로 출력이 가능합니다.

 

 

BFS함수에서도 주석으로 거의 다 설명이 가능할 것 같습니다.

 

1. 시작 노드를 큐에 넣고 방문 표시를 합니다.
2.  큐에서 노드를 꺼내 해당 노드와 연결된 모든 인접 노드를 큐에 넣습니다. 이때 방문하지 않은 노드만 큐에 넣습니다. 
3. 2번 과정을 큐가 빌 때까지 반복합니다. 
4. 큐가 빌 경우, 시작 노드에서 모든 노드를 방문했다는 의미이므로 탐색을 종료합니다.

BFS는 위와 같이 진행됩니다. 간단히 정리하자면 다음과 같습니다.

큐에서 꺼내고 꺼낸 노드의 자식들을 큐에 추가하고 꺼낸 노드는 출력❗️

 

코드를 설명하자면 처음에는 입력으로 받은 정점을 큐에 추가를 해준 뒤 정점을 방문처리해 주고, 해당 정점(node)을 출력을 해줍니다.

 

그리고 큐가 비워질 때까지 반복하는 데 앞서 말한 동작방식대로 큐에서 꺼내고, 꺼낸 정점과 전체 정점을 순회하면서 인접한 정점들을 큐에 넣어줍니다.

 

전체 정점을 순회하면서 큐에서 꺼낸 정점과 연결된 정점이면서, 아직 방문하지 않은 정점이라면 해당 정점을 큐에 넣어주고, 출력해 줍니다.

 

말보다 직접 동작하는 방식을 보면 이해가 더 쉬울 것 같습니다. 예제 입력2

---

BFS 알고리즘의 진행 과정

• 1) 시작 노드는 3번 노드입니다.
• 2) 3번 노드를 방문하고 큐에 넣습니다.
  • 큐: [3]
• 3) 큐에서 노드를 꺼내 인접 노드를 탐색합니다.
  • 3번 노드의 인접 노드: 1, 4
  • 1번 노드를 큐에 넣습니다.
  • 4번 노드를 큐에 넣습니다.
• 4) 큐: [1, 4] 큐에서 노드를 꺼내 인접 노드를 탐색합니다.
  • 1번 노드의 인접 노드: 2, 3
  • 2번 노드를 큐에 넣습니다.
  • 큐: [4, 2]
• 5) 큐에서 노드를 꺼내 인접 노드를 탐색합니다.
  • 4번 노드의 인접 노드: 3, 5
  • 5번 노드를 큐에 넣습니다.
  • 큐: [2, 5]
• 6)  큐에서 노드를 꺼내 인접 노드를 탐색합니다.
  • 2번 노드의 인접 노드: 1, 5
  • 큐: [5]
• 7) 큐에서 노드를 꺼내 인접 노드를 탐색합니다.
  • 5번 노드의 인접 노드: 2, 4
  • 큐: []
• 따라서, BFS 결과는 3 1 4 2 5입니다.