[백준] 14496번 - 그대, 그머가 되어 (Java)

 

https://www.acmicpc.net/problem/14496

14496번: 그대, 그머가 되어

<문제 분석>
문자열 a를 b로 바꾸는 최소 치환 횟수를 구하는 문제이다.
문자열 관련 문제처럼 보이나 실상은 문자열 a에서 b로 가는 최단경로를 구하는 문제이다.

우선순위 큐와 다익스트라 알고리즘을 사용해서 풀면된다.
인접리스트 방식 둘로 나눠서 풀어보자.

<풀이>
1. class Node를 구성하자. cost로 오름차순으로 PQ를 구성한다.
2. 방문배열(boolean visited[])선언한다.
3. 입력합수에서 인접리스트 방식으로 구성한다.
4. 다익스트라 알고리즘 시작한다.
  - 시작점을 큐에 넣고 방문처리한다. 거리는 0.
  - 큐에 든 노드가 없을 때까지 루프 시작
  - 큐에서 꺼내서 연결된 정점으로 이동 시 거리 계산
  - 이미 방문한 곳이면 스킵
  - 현재까지 진행한 거리 + 1해서 업데이트
  - 방문배열 업데이트
  - 큐에 삽입

 

 

 

 

<코드 구현 - 일반큐>

import java.util.Scanner;
import java.io.IOException;
import java.util.Arrays;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;
import java.util.LinkedList;

//[백준] 14496번 - 그대, 그머가 되어 (Java)

public class Main {
    static int A, B, N, M;
    static List<ArrayList<Node>> graph;
    static boolean visited[];

    public class Node {
        int end;
        int cost;
        Node (int end, int cost) {
            this.end = end;
            this.cost = cost;
        }
    }
    
    public void InputData() throws IOException {
        Scanner sc = new Scanner(System.in);
        A = sc.nextInt();
        B = sc.nextInt();
        N = sc.nextInt();
        M = sc.nextInt();

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

        for (int i=0; i<M; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            graph.get(a).add(new Node(b, 1));
            graph.get(b).add(new Node(a, 1)); // 무방향 그래프이므로 반대상황도 삽입한다.
        }
    }

    public void Dijkstra(int start) {
        Queue<Node> Q = new LinkedList<>();
        Q.add(new Node(start, 0));
        visited[start] = true;

        while(!Q.isEmpty()) {
            Node now = Q.poll();

            // 목적지에 도착했으면 탐색 중지
            if (now.end == B) {
                System.out.println(now.cost);
                return;
            };

            for (Node next : graph.get(now.end)) {
                if (visited[next.end]) continue; // 방문한 정점이면 스킵
                visited[next.end] = true;
                Q.add(new Node(next.end, now.cost+1));
            }
        }
        System.out.println(-1);
    }

	public void Solve() {
        visited = new boolean[N+1]; // 방문배열 초기화
        Dijkstra(A); // 시작점에서 다익스트라 함수 실행
	}
    
	public static void main(String[] args) throws IOException
	{
		Main m = new Main();
		m.InputData();///입력
		//코드를 작성하세요
        m.Solve();
	}
}

 

<제출 결과>

 

<코드 구현 - 우선순위큐>

import java.util.Scanner;
import java.io.IOException;
import java.util.Arrays;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;
import java.util.LinkedList;
import java.util.PriorityQueue;

//[백준] 14496번 - 그대, 그머가 되어 (Java)

public class Main {
    static int A, B, N, M;
    static List<ArrayList<Node>> graph;
    static boolean visited[];

    public class Node implements Comparable<Node> {
        int end;
        int cost;
        Node (int end, int cost) {
            this.end = end;
            this.cost = cost;
        }

        @Override
        public int compareTo(Node o) {
            return this.cost - o.cost;
        }
    }
    
    public void InputData() throws IOException {
        Scanner sc = new Scanner(System.in);
        A = sc.nextInt();
        B = sc.nextInt();
        N = sc.nextInt();
        M = sc.nextInt();

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

        for (int i=0; i<M; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            graph.get(a).add(new Node(b, 1));
            graph.get(b).add(new Node(a, 1)); // 무방향 그래프이므로 반대상황도 삽입한다.
        }
    }

    public void Dijkstra(int start) {
        //Queue<Node> Q = new LinkedList<>();
        PriorityQueue<Node> Q = new PriorityQueue<>();
        Q.add(new Node(start, 0));
        visited[start] = true;

        while(!Q.isEmpty()) {
            Node now = Q.poll();

            // 목적지에 도착했으면 탐색 중지
            if (now.end == B) {
                System.out.println(now.cost);
                return;
            };

            for (Node next : graph.get(now.end)) {
                if (visited[next.end]) continue; // 방문한 정점이면 스킵
                visited[next.end] = true;
                Q.add(new Node(next.end, now.cost+1));
            }
        }
        System.out.println(-1);
    }

	public void Solve() {
        visited = new boolean[N+1]; // 방문배열 초기화
        Dijkstra(A); // 시작점에서 다익스트라 함수 실행
	}
    
	public static void main(String[] args) throws IOException
	{
		Main m = new Main();
		m.InputData();///입력
		//코드를 작성하세요
        m.Solve();
	}
}

 

<제출 결과>

-> 일반 큐를 사용했을 때 보다 36ms 절감 효과