깊이 우선 탐색 - DFS(Depth-First Search) - dijkstra 다익스트라

DFS(Depth-First Search)는 깊이 우선 탐색 알고리즘으로, 그래프나 트리에서 한 경로를 끝까지 탐색한 후, 다른 경로로 이동하며 탐색하는 방식입니다. DFS는 재귀 또는 스택을 이용해 구현됩니다.

 

 

• 재귀 호출 또는 스택을 사용해 구현.
• 깊이 우선으로 탐색하며, 한 정점을 끝까지 방문한 뒤 돌아옴.
• 경로의 끝까지 도달하거나 특정 조건을 만족할 때 종료 가능.

public class MazeSolverDFS {
    private static final int[] dx = {-1, 1, 0, 0}; // 상, 하, 좌, 우
    private static final int[] dy = {0, 0, -1, 1};
    private static boolean found = false;

    public static void main(String[] args) {
        int[][] maze = {
                {0, 1, 0, 0, 0},
                {0, 1, 0, 1, 0},
                {0, 0, 0, 1, 0},
                {0, 1, 1, 1, 0},
                {0, 0, 0, 0, 0}
        };

        boolean[][] visited = new boolean[maze.length][maze[0].length];
        dfs(maze, visited, 0, 0, 4, 4);
        System.out.println("경로를 찾았는가? " + found); // 출력: 경로를 찾았는가? true
    }

    public static void dfs(int[][] maze, boolean[][] visited, int x, int y, int endX, int endY) {
        if (x < 0 || y < 0 || x >= maze.length || y >= maze[0].length || visited[x][y] || maze[x][y] == 1) {
            return;
        }

        // 목표 지점 도달
        if (x == endX && y == endY) {
            found = true;
            return;
        }
        visited[x][y] = true;
        // 상하좌우 탐색
        for (int i = 0; i < 4; i++) {
            dfs(maze, visited, x + dx[i], y + dy[i], endX, endY);
        }
        // 백트래킹
        visited[x][y] = false;
    }
}

 

 

 

---

다익스트라(Dijkstra)

 

다익스트라(Dijkstra) 알고리즘은 가중치가 있는 그래프에서 한 정점에서 다른 정점들까지의 최단 경로를 찾는 알고리즘입니다. 이 알고리즘은 음수 가중치가 없는 경우에만 사용할 수 있습니다.

 

 

• 우선순위 큐(PriorityQueue) 사용
  • 현재 가장 작은 거리를 가지는 노드를 빠르게 찾기 위해 PriorityQueue를 사용합니다.
  • compareTo 메서드를 구현하여 거리 기준으로 정렬합니다.
• 거리 테이블(HashMap) 초기화
  • 출발 노드(start)는 0, 나머지 노드는 Integer.MAX_VALUE(무한대)로 초기화합니다.
• 다익스트라 반복 과정
  • PriorityQueue에서 가장 짧은 거리의 노드를 꺼내 방문합니다.
  • 해당 노드를 통해 인접한 노드들의 거리를 갱신합니다.
  • 거리가 갱신되었다면 다시 PriorityQueue에 추가합니다.
• 최단 거리 출력
  • 최종적으로 출발 노드에서 각 노드까지의 최단 거리를 출력합니다.

 

 

import java.util.*;

public class DijkstraExample {
    public static void main(String[] args) {
        // 그래프 정의 (노드 번호는 1부터 시작)
        int n = 6; // 노드 수
        List<List<Edge>> graph = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<>());
        }

        // 간선 추가 (양방향 그래프)
        graph.get(1).add(new Edge(2, 2));
        graph.get(1).add(new Edge(3, 4));
        graph.get(2).add(new Edge(3, 1));
        graph.get(2).add(new Edge(4, 7));
        graph.get(3).add(new Edge(5, 3));
        graph.get(4).add(new Edge(6, 1));
        graph.get(5).add(new Edge(4, 2));
        graph.get(5).add(new Edge(6, 5));

        // 다익스트라 실행
        int start = 1;
        int[] distances = dijkstra(graph, n, start);

        // 결과 출력
        System.out.println("최단 거리:");
        for (int i = 1; i <= n; i++) {
            System.out.println("1번 노드에서 " + i + "번 노드까지의 거리: " +
                               (distances[i] == Integer.MAX_VALUE ? "도달 불가" : distances[i]));
        }
    }
	//시작점에서 모든 노드의 최단거리 측정
    public static int[] dijkstra(List<List<Edge>> graph, int n, int start) {
        int[] distances = new int[n + 1];
        Arrays.fill(distances, Integer.MAX_VALUE);
        distances[start] = 0;

        PriorityQueue<Edge> pq = new PriorityQueue<>((a, b) -> a.weight - b.weight);
        pq.add(new Edge(start, 0));

        while (!pq.isEmpty()) {
            Edge current = pq.poll();
            int currentNode = current.to;
            int currentWeight = current.weight;

            if (currentWeight > distances[currentNode]) {
                continue;
            }

            for (Edge edge : graph.get(currentNode)) {
            	//newDistance = 시작노드(A)부터 현재노드(B)의 거리 + 현재노드(B)부터 다음노드(C)까지의 거리
                int newDistance = distances[currentNode] + edge.weight;
				
                //시작노드(A)부터 현재노드(B)의 거리 + 현재노드(B)부터 다음노드(C) < 시작노드(A)부터 다음노드(C)까지의 거리 
                if (newDistance < distances[edge.to]) {
                    distances[edge.to] = newDistance;
                    pq.add(new Edge(edge.to, newDistance));
                }
            }
        }

        return distances;
    }

    static class Edge {
        int to, weight;

        Edge(int to, int weight) {
            this.to = to;
            this.weight = weight;
        }
    }
}