[백준] 1260번 DFS와 BFS 자바

문제 (실버2)

 

 

1260번: DFS와 BFS

 

 

문제 풀이

 

이 문제는 진짜 제목 그대로 DFS와 BFS를 직접 구현해보는 문제이다. 코딩테스트 연습을 하다보면 자주 접하게 되는 개념이지만, 어려워서 항상 코드를 보고 풀었다. 이번 기회에 DFS와 BFS개념을 확실히 다지고자 풀게되었다. 이번 기회에 개념 꼭 다지고 넘어가야지!

 

우선 DFS알고리즘은 깊이 우선 탐색으로 스택을 이용하는 방법과 재귀함수를 이용하는 방법 두가지가 있는데, 대부분 재귀함수를 이용하는 것이 보편적이라 재귀함수를 이용해서 풀었다.

 

1. 일단 두 정점이 연결된 노드번호를 받아서 각 정점마다 인접한 노드번호를 list의 값으로 넣는다. 

  그리고 각 정점에 대해 방문했는지 여부를 알기 위해 boolean형 visited배열을 선언한다.

 

 

 

2. 시작 정점(1번)의 값부터 방문하기 시작한다. 1번은 방문되었으므로 visited[1]은 true가 됨.

 

 

 

3. 시작 정점의 인접한 노드들부터 차례대로 탐색한다. (작은 수부터 리스트에 들어가있어야 함)

   따라서 2번이 다음으로 방문되어 visited배열을 업데이트한다.

 

 

4. 2번 노드의 다음 인접노드인 1은 이미 visited가 true이므로 다음 인접 노드인 4번을 방문한다. 

 

 

 

5. 4번 노드의 1,2번 노드는 이미 방문이 되었으므로 3번 노드를 방문한다.

 

6. 이제 모든 정점이 방문이 되었으므로 DFS는 더이상 호출되지 않고 종료가 된다.

 

 

 

BFS알고리즘은 너비 우선 탐색으로 Queue를 사용하여 문제를 해결했다. 자바에서 Queue는 LinkedList(연결리스트)를 이용한다.

 

LinkedList는 각 노드가 데이터와 포인터를 가지고 연결되어있는 자료구조이다.

- 인덱스 개념이 없어 특정요소에 접근하기 위해서는 순차탐색 필요

- 데이터 추가/삭제 시 앞뒤 노드의 링크만 바꾸면 되므로 추가삭제 용이

- 탐색이나 정렬을 자주하는 경우 -> 배열 사용

- 데이터 추가/삭제가 많은 경우 -> 연결리스트 사용

 

1. 시작정점인 1번부터 방문을 시작한다. 1번을 큐에 넣고 visited배열을 true로 만든다.

2. 1번의 인접한 노드인 2,3,4번을 큐에 다 넣는다.

3. 큐에서 데이터를 차례대로 꺼내면서 꺼낸 수의 인접노드 방문여부를 확인 후 방문이 안되었으면 큐에 넣는다.

 

 

 

소스 코드

 

import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class b_1260 {

	static ArrayList<Integer>[] list;
	static boolean[] visited;
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int N = sc.nextInt();	// 정점 개수
		int M = sc.nextInt();	// 간선 개수
		int V = sc.nextInt();	// 시작 정점
        
		// ArrayList배열 초기화. 정점의 번호대로 인덱스를 맞추기 위해 N+1 크기로 생성
		list = new ArrayList[N+1];
		for(int i = 1; i < N+1; i++)
			list[i] = new ArrayList<Integer>();
		
		for(int i = 0; i < M; i++) {
			int u = sc.nextInt();
			int v = sc.nextInt();
			list[u].add(v);
			list[v].add(u);
		}
		
		//작은 정점부터 차례차례 방문하므로 정렬 필요
		for(int i = 1; i < N+1; i++)
			Collections.sort(list[i]);	// ArrayList정렬 메소드
		
		visited = new boolean[N+1]; // 정점 방문여부를 위해 정점개수와 맞게 배열생성(초기값 false)
		DFS(V);						// 시작 정점부터 깊이우선탐색 시작
		System.out.println();
		
		visited = new boolean[N+1]; // 방문배열 다시 초기화
		BFS(V);						// 시작 정점부터 너비우선 탐색 시작
		
		sc.close();
	}
	
	static void DFS(int x) {
		if(visited[x])	
			return;		// 이미 방문한 곳이라면 바로 리턴
		
		visited[x] = true;	// 아니면 방문했다고 표시
		System.out.print(x + " ");
		
		for(int y : list[x])	// 방문 정점과 이어진 다른 정점들 하나하나 확인
			if(!visited[y])		// 아직 방문이 안되었다면
				DFS(y);			// 계속 깊이 이어가기
	}
	
	static void BFS(int x) {
		Queue<Integer> q = new LinkedList<Integer>();	// 큐생성
		q.add(x);	// 정점 큐에 넣기
		visited[x] = true;	// 정점 방문했다고 표시
		
		int n;
		while(!q.isEmpty()) {	// 큐 빌 때까지 반복
			n = q.poll();		// 큐의 첫번째 값 빼내기
			System.out.print(n + " ");	
			
			for(int y : list[n]) {	// 첫번째 방문 정점의 인접한 정점들 확인
				if(!visited[y]) {	// 방문하지 않았다면
					q.add(y);		// 큐에 넣고
					visited[y] = true; // 방문표시
				}
			}
			// 첫번째 정점과 인접한 애들 다 큐에 넣고, 다시 위로 올라가 
            		// 그 값들을 다시 큐에서 빼내면서 인접한 값의 인접한 애들 큐에 넣기..
		}		
	}

}