[알고리즘] 묘공단 깊이 우선 탐색 순회

문제 정보

묘공단 402페이지 예제

 

문제 설명

깊이 우선 탐색으로 모든 그래프의 노드를 순회하는 함수를 작성하시오

시작 노드 start, graph는 [출발, 도착] 쌍들이 들어있는 리스트다. 

반환 값은 그래프의 시작 노드부터 깊이 우선 탐색으로 진행한 순서대로 노드가 저장된 리스트이다.

 

입출력 예제

graph

{1, 2}, {2, 3}, {3, 4}, {4, 5}

 

start

1

 

n

5

 

result

{ 1, 2, 3, 4, ,5}

import java.util.*;
import java.util.stream.Collectors;

public class Solution {

    public static void main(String[] args) {
        for (int item : new Solution().solution(new int[][]{{1, 2}, {2, 3}, {3, 4}, {4, 5}}, 1, 5)) {
            System.out.println(item);
        }
    }
    
    public int[] solution(int [][] graph, int start, int n)
    {
    	// 방문 여부 체크
        boolean[] visited = new boolean[n + 1];
		
        // 인접 리스트 초기화
        ArrayList<Integer> answer = new ArrayList();
	
    	
        ArrayList<Integer>[] adjust = new ArrayList[n + 1];

		// 그래프를 인접 리스트로 변환
        for (int i = 0; i < adjust.length; i++) {
            adjust[i] = new ArrayList();
        }

		// DFS를 순회한 결과를 반환
        for (int[] edge : graph) {
            adjust[edge[0]].add(edge[1]);
        }
		
        // DFS 탐색 메서드
        dfs(start, visited, answer, adjust);
		
        // DFS 탐색 결과 반환
        return answer.stream().mapToInt(Integer::intValue).toArray();
    }

    private void dfs(int now, boolean[] visited, ArrayList answer, ArrayList<Integer>[] adjust) {
    	// 방문 체크
        visited[now] = true;
		
        // 계속 1번째로 걸리는 노드를 잡고 끝까지 타고 가다가 마지막인 경우 아래 반복문으로 되돌아가서 원소가 있으면 또 실행한다.
        answer.add(now);
        
		// 인접 노드를 뿌려준다.
        for (int next : adjust[now]) {
        	// 방문한 경우 이미 인접노드를 뿌렸기 때문에 재귀 호출하지 않는다.
            if (!visited[next]) {
                dfs(next, visited, answer, adjust);
            }
        }
    }
}