[1260][java][백준]DFS와BFS

[1260][java][백준]DFS와BFS

그래프를 탐색하기 위한 대표적인 알고리즘 - DFS , BFS (이해하려면 스택,큐,재귀함수를 알아야한다)

▶ 탐색 Search

많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 의미한다.

▶ 자료구조 Data Structure

데이터를 표현하고 관리하고 처리하기 위한 구조를 의미한다.

삽입(Push) : 데이터를 삽입한다.

삭제(Pop) : 데이터를 삭제한다.

▶ 스택(Stack)

박스 쌓기에 비유

선입후출(First In Last Out)

▒ java ▒

* 자바에서 스택의 최상단 원소를 출력할때 peek() 메서드사용

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 import java util. * ; public calss Main{ public static void main( String [] args){ Stack < Integer > s = new Stack < > (); // 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제() s.push( 5 ); s.push( 2 ); s.push( 3 ); s.push( 7 ); s.pop(); s.push( 1 ); s.push( 4 ); s.pop(); // 스택의 최상단 원소부터 출력 while ( ! s.empty()){ System . out . print (s.peek() + " " ); s.pop(); } } } Colored by Color Scripter cs

▶ 큐(Queue)

입구와 출구가 모두 뚫려 있는 터널로 비유

선입선출(First In First Out)

▒ java ▒

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 import java util. * ; public calss Main{ public static void main( String [] args){ Queue < Integer > q = new LinkedList < > (); // 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제() s.offer( 5 ); s.offer( 2 ); s.offer( 3 ); s.offer( 7 ); s.poll(); s.offer( 1 ); s.offer( 4 ); s.poll(); // 먼저 들어온 원소부터 출력 while ( ! q.empty()){ System . out . print (q.poll() + " " ); } } } Colored by Color Scripter cs

▶ 재귀 함수 Recursive Function

자기 자신을 다시 호출하는 함수

재귀 함수를 문제 풀이에서 사용할 시 재귀 함수가 언제 끝날지, 종료 조건을 꼭 명시해야 한다.

◈ DFS

- Depth-First-Search , 깊이 우선 탐색

- 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다.

* 그래프는 노드(Node) 와 간선(Edge) 로 표현되며 이때 노드를 정점(Vertex) 라고도 한다

* 프로그래밍에서 그래프는 크게 2가지 방식으로 표현

1. 인접 행렬 (Adjacency Matrix) : 2차원 배열로 그래프의 연결 관계를 표현하는 방식

- 2차원 배열에 각 노드가 연결된 형태를 기록하는 방식

2. 인접 리스트 (Adjacency List) : 리스트로 그래프의 연결 관계를 표현하는 방식

- 연결리스트 자료구조를 이용하여 구현하는데 C++나 자바는 별도로 연결 리스트 기능을 위한 표준 라이브러리를 제공한다

DFS는 스택 자료구조를 이용하며 구체적인 동작 과정은 다음과 같다

① 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.

② 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리를 한다.

방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.

③ ②번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.

- DFS 는 스택 자료구조에 기초한다는 점에서 구현이 간단하다. 실제로는 스택을 쓰지 않아도 되며 탐색을 수행함에 있어서 데이터의 개수가 N개의 경우 O(N) 의 시간이 소요된다는 특징이 있다. 또한 재귀 함수를 이용했을 때 매우 간결하게 구현할 수 있다.

▒ DFS.py ▒

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 # 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) # 각 노드가 연결된 정보를 리스트 자료형으로 표현(2차월 리스트) graph = [ [], [ 2 , 3 , 8 ], [ 1 , 7 ], [ 1 , 4 , 5 ], [ 3 , 5 ], [ 3 , 4 ], [ 7 ], [ 2 , 6 , 8 ], [ 1 , 7 ] ] # 각 노드가 방문된 정보를 리스트 자료형으로 표현(1차원 리스트) visited = [ False ] * 9 # 정의된 DFS 함수 호출 dfs(graph, 1 , visited) cs

from http://eonhwa-theme.tistory.com/30 by ccl(S) rewrite - 2021-10-30 22:00:38