99클럽 코테 스터디 10일차(다익스트라 + BFS)

문제: https://www.acmicpc.net/problem/18352

🚨 오늘의 학습

⭐️다익스트라⭐️

최단 경로 알고리즘
한개의 시작 노드로 부터 노드까지의 최단경로를 구함

⭐️최단 경로⭐️

BFS(너비 우선 탐색) - 수평적 구조:
출발 노드에서 가까운 노드부터 탐색을 진행합니다.
최단 경로 자체가 수평적 구조이므로 BFS에 적합

✼ DFS(깊이 우선 탐색) - 수직적구조:
출발 노드에서 가장 깊은 노드까지 탐색을 계속하기 때문에 최단 경로가 아닌 더 긴 경로를 먼저 탐색하게 될 가능성이 큽니다.

🗝️ 🔅Node 클래스

 public static class Node implements Comparable<Node>{
        int index; // 노드
        int cost; // 가중치

        public Node(int start, int cost) {
            this.index = start;
            this.cost = cost;
        }

        @Override
        public int compareTo (Node node) {
            return Integer.compare(this.cost, node.cost);
        }
    }

🗝️ graph

ArrayList<ArrayList<Node>> graph = new ArrayList<>();

🗝️ 우선순위 큐

PriorityQueue<Node> pq = new PriorityQueue<>();
pq.offer(new Node(시작 노드, 0));

🗝️ 노드간 거리

int[] dist = new int[node+1];
Arrays.fills(dist,INF);

🗝️ 🔅정점 탐색(BFS)

while (!pq.isEmpty()) {
            int nowVertex = pq.poll().index;

            if (visited[nowVertex]) continue;  // 이미 방문한 정점이면 넘어감
            visited[nowVertex] = true;  // 방문 처리

            // 현재 정점과 연결된 정점들 탐색
            for (Node next : graph.get(nowVertex)) {
                if (dist[next.index] > dist[nowVertex] + next.cost) {
                    dist[next.index] = dist[nowVertex] + next.cost;  // 거리 업데이트
                    pq.offer(new Node(next.index, dist[next.index]));  // 우선순위 큐에 추가
                }
            }

        }

오늘의 회고

• 거리의 방향이 단방향이라 다익스트라로 구현 가능할 지 의문이 들었지만
  무방향에서 graph에서 단방향 - 단방향으로 양방향 을 생성했는데
  이부분을 단방향으로만 처리해서 구현 할 수 있었다.
• 최단 경로의 경우에는