깊이 우선 탐색 - 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) 알고리즘은 가중치가 있는 그래프에서 한 정점에서 다른 정점들까지의 최단 경로를 찾는 알고리즘입니다. 이 알고리즘은 음수 가중치가 없는 경우에만 사용할 수 있습니다.

 

 

• 최소 거리 노드 선택:
  • 우선순위 큐를 사용해 매번 가장 작은 거리의 노드를 효율적으로 선택.
• 거리 업데이트:
  • 현재 노드까지의 거리와 인접 노드 간 거리를 합산하여 최소 거리 갱신.

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)) {
                int newDistance = distances[currentNode] + edge.weight;

                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;
        }
    }
}