BOJ14496 그대, 그머가 되어

https://www.acmicpc.net/problem/14496 (opens new window)

머호는 문자 a를 문자 b로 바꾸려하고, N개의 문자와 치환 가능한 문자쌍 M개가 있다. 머호에게 a를 b로 바꾸기 위한 치환의 최소 횟수를 구해서 머호에게 알려주자!

Node.java

노드에 대한 정보를 관리하기 위한 Node 클래스이다.

private static class Node {
    private int index;
    private int distance;

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

다익스트라 활용

최단 경로 탐색을 위한 다익스트라 메소드이다.

private static void dijkstra(int start) {
    PriorityQueue<Node> priorityQueue = new PriorityQueue<>((o1, o2) -> {
        if (o1.distance < o2.distance) {
            return -1;
        } else if (o1.distance == o2.distance) {
            return 0;
        }
        return 1;
    });

    priorityQueue.offer(new Node(start, 0));
    d[start] = 0;

    while (!priorityQueue.isEmpty()) {
        Node node = priorityQueue.poll();
        int now = node.index;
        int distance = node.distance;

        if (d[now] < distance) {
            continue;
        }

        for (int i = 0; i < graph.get(now).size(); i++) {
            int cost = d[now] + graph.get(now).get(i).distance;
            if (cost < d[graph.get(now).get(i).index]) {
                d[graph.get(now).get(i).index] = cost;
                priorityQueue.offer(new Node(graph.get(now).get(i).index, cost));
            }
        }
    }
}

PriorityQueue의 경우 Comparator를 사용하면 더욱 짧게 줄일 수 있다.

PriorityQueue<Node> priorityQueue = new PriorityQueue<>(Comparator.comparingInt(node -> node.distance));

제출 코드

graph를 초기화 한 후 양방향으로 노드를 세팅해준다. 거리의 경우 추가적으로 제공된 것이 없기 때문에 1로 세팅한다.

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

for (int i = 0; i < m; i++) {
    int inputA = scanner.nextInt();
    int inputB = scanner.nextInt();

    graph.get(inputA).add(new Node(inputB, 1)); 
    graph.get(inputB).add(new Node(inputA, 1));
}

최단 거리 저장을 위한 배열을 모두 INF로 채우고 경로 탐색을 위한 dijkstra 메소드를 활용한다. 탐색이 완료되면 치환 횟수를 조회하여 출력한다.

Arrays.fill(d, INF);

dijkstra(a);

if (d[b] == INF) {
    System.out.println(-1);
} else {
    System.out.println(d[b]);
}

아래는 최종 제출 코드이다.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Scanner;

public class BOJ14496 {

    public static final int INF = Integer.MAX_VALUE;
    private static final List<List<Node>> graph = new ArrayList<>();
    private static final int[] d = new int[1_001];

    private static class Node {
        private int index;
        private int distance;

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

    private static void dijkstra(int start) {
        PriorityQueue<Node> priorityQueue = new PriorityQueue<>(Comparator.comparingInt(node -> node.distance));

        priorityQueue.offer(new Node(start, 0));
        d[start] = 0;

        while (!priorityQueue.isEmpty()) {
            Node node = priorityQueue.poll();
            int now = node.index;
            int distance = node.distance;

            if (d[now] < distance) {
                continue;
            }

            for (int i = 0; i < graph.get(now).size(); i++) {
                int cost = d[now] + graph.get(now).get(i).distance;
                if (cost < d[graph.get(now).get(i).index]) {
                    d[graph.get(now).get(i).index] = cost;
                    priorityQueue.offer(new Node(graph.get(now).get(i).index, cost));
                }
            }
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int a = scanner.nextInt(); // 문자 a
        int b = scanner.nextInt(); // 문자 b

        int n = scanner.nextInt(); // 전체 문자 수 n (노드)
        int m = scanner.nextInt(); // 치환 가능한 문자쌍의 수 m (간선)

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

        for (int i = 0; i < m; i++) {
            int inputA = scanner.nextInt();
            int inputB = scanner.nextInt();

            graph.get(inputA).add(new Node(inputB, 1)); 
            graph.get(inputB).add(new Node(inputA, 1));
        }

        Arrays.fill(d, INF);

        dijkstra(a);

        if (d[b] == INF) {
            System.out.println(-1);
        } else {
            System.out.println(d[b]);
        }
    }
}

BFS 활용

// TODO

#algorithm #BOJ #그래프 이론 #그래프 탐색 #너비 우선 탐색 #다익스트라 #최단 경로 알고리즘 #TODO