[백준,BOJ 1260] DFS와 BFS(JAVA 구현, 재풀이)

 

 

-풀이 

  이전에 풀이했던 DFS, BFS문제는 그래프의 구현을 위해 인접 행렬을 사용한 경험이 있었기 때문에, 이번에는 인접 리스트로 그래프를 구현해 풀어보고자 했다.

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

class Main {
  
    // DFS 메소드
	static void dfs(ArrayList<ArrayList<Integer>> a, boolean[] check, int v) {
		if(check[v] == true) return; // 재귀호출 종료 부, 방문한 적이 있으면 메소드 종료
		
		check[v] = true; // 방문한 적 없는 정점이라면 방문 처리
		System.out.print(v+" "); // 방문했기 때문에 정점 출력
		
        // 바깥쪽 ArrayList의 인덱스인 정점과 연결된 정점을 탐색
		for(int i = 0;i<a.get(v).size();i++) { 
			if(!check[a.get(v).get(i)])  // 연결된 정점이 방문한 적 없다면
				dfs(a,check,a.get(v).get(i)); // 재귀호출로 깊이 우선 탐색 실행
		}
	}
	
    // BFS 메소드
	static void bfs(ArrayList<ArrayList<Integer>> a, boolean[] check, int v) {
		Queue<Integer> q = new LinkedList<>(); // BFS를 위한 큐 객체
		
		q.add(v); // 시작 정점을 큐에 삽입
		check[v] = true; // 방문처리를 한다. 
		
		while(!q.isEmpty()) { // 큐가 빌 때 까지 반복
			v = q.poll(); // 큐에 삽입되어 있는 정점을 하나 가져온다.
			System.out.print(v+" "); // 해당 정점을 출력
			
            // 바깥쪽 ArrayList의 인덱스인 정점과 연결된 정점을 탐색해 모두 큐에 삽입
			for(int i = 0;i<a.get(v).size();i++) {
				if(!check[a.get(v).get(i)]) { // 방문하지 않았던 정점이라면
					q.add(a.get(v).get(i)); 
					check[a.get(v).get(i)] = true; // 해당 정점을 방문 처리한다. 
				}
			}
		}
	}
	
	public static void main(String[] args)  {
		Scanner in = new Scanner(System.in);
		
		int n = in.nextInt(); // 정점의 수
		int m = in.nextInt(); // 간선의 수
		int v = in.nextInt(); // 시작 정점
		
         // 인접 리스트를 위한 ArrayList, ArrayList안에 ArrayList를 사용하였다.
		ArrayList<ArrayList<Integer>> a = new ArrayList<ArrayList<Integer>>();
        
        // 각 정점 방문 여부를 판단 할 배열
		boolean check[] = new boolean[n+1];
		
        // ArrayList 객체 안에 요소로써 ArrayList 객체를 생성
		for(int i=0;i<=n;i++) {
			a.add(new ArrayList<Integer>());
		}
		
        // 정점의 연결 정보를 입력
		for(int i=0;i<m;i++) {
			int v1 = in.nextInt();
			int v2 = in.nextInt();
			
			a.get(v1).add(v2);
			a.get(v2).add(v1);
			
		}
		
        // 이동 경우의 수가 다수 존재할 경우 작은 정점부터 이동해야 하므로 인접 리스트를 오름차순 정렬
		for(int i=1;i<=n;i++) {
			Collections.sort(a.get(i));
		}
		
		// DFS 호출
		dfs(a,check,v);
        // 방문여부 배열을 BFS를 위해 다시 false로 초기화
		Arrays.fill(check, false);
		System.out.println();
        // BFS 호출
		bfs(a,check,v);
		   
	  }
}

 

  처음 인접 리스트를 사용할 때 다른 블로그들의 정보를 찾아 보니

ArrayList<Integer>[] a = (ArrayList<Integer>[]) new ArrayList[n + 1];
	for (int i = 0; i <= n; i++) { 
    	a[i] = new ArrayList<>(); 
    }

  이와 같이 사용하는 것을 볼 수 있었는데, 개인적으로 ArrayList <Integer>[] 이 부분이 무엇을 의미하며 어떻게 자료가 구성되는지 이해가 되질 않아 아래와 같은 방법을 사용하게 되었다.

ArrayList<ArrayList<Integer>> a = new ArrayList<ArrayList<Integer>>();		
		for(int i=0;i<=n;i++) {
			a.add(new ArrayList<Integer>());
		}

  이것이 의미하는 것은 ArrayList 객체의 요소로 ArrayList 객체가 생성된다는 의미로 이해할 수 있었고, 바깥쪽의 ArrayList의 인덱스가 각 정점의 번호를 의미하며, 안쪽에 생긴 ArrayList에 해당 정점에 연결된 정점 정보를 담아 구성된다고 이해할 수 있었기 때문에 이와 같은 방식을 사용하였다.