Collections.sort(리스트) : 리스트를 오름차순 정렬
Iterator : 컬렉션에 저장된 요소들을 읽어오는 방법
< 선언하는 방법 >
Iterator<Integer> 변수명 = 리스트명.⊙();
⊙ listIterator : 양방향 이동 가능
( ArrayList나 LinkedList와 같은 List 인터페이스를 구현한 컬렉션만 가능 )
⊙ iterator() : 단방향 이동
-> .hasNext() : 읽어 올 요소가 있으면 True, 없으면 False
-> .next() : 다음 요소를 읽어 옴
-> .remove() : next()로 읽어온 요소를 삭제
구현
import java.util.*;
public class javatest {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(); // 정점의 개수
int m = sc.nextInt(); // 간선의 개수
int v = sc.nextInt(); // 탐색을 시작할 정점의 번호
boolean visited[] = new boolean[n + 1]; // 방문 여부를 검사할 배열
LinkedList<Integer>[] adjList = new LinkedList[n + 1];
for (int i = 0; i <= n; i++) {
adjList[i] = new LinkedList<Integer>();
}
// 두 정점 사이에 여러 개의 간선이 있을 수 있다.
// 입력으로 주어지는 간선은 양방향이다.
for (int i = 0; i < m; i++) {
int v1 = sc.nextInt();
int v2 = sc.nextInt();
adjList[v1].add(v2);
adjList[v2].add(v1);
}
// 방문 순서를 위해 오름차순 정렬
for (int i = 1; i <= n; i++) {
Collections.sort(adjList[i]);
}
System.out.println("DFS - 깊이 우선 탐색");
DFS(v, adjList, visited);
}
// DFS( 재귀 함수 )
public static void DFS(int v, LinkedList<Integer>[] adjList, boolean[] visited) {
visited[v] = true; // 정점 방문 표시
System.out.print(v + " "); // 정점 출력
Iterator<Integer> iter = adjList[v].listIterator(); // 정점 인접리스트 순회
while (iter.hasNext()) {
int w = iter.next();
if (!visited[w]) { // 방문하지 않은 정점이라면
DFS(w, adjList, visited); // 다시 DFS
}
}
}
}
결과
