[Java] Boj 14496: 그대, 그머가 되어

문제

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

 

풀이

 주어진 문자를 얼마나 적은 횟수로 변환시켜서 원하는 문자로 변환할 수 있는지 최소 변환 횟수를 구하는 문제이다. 문제 이해가 조금 난해할 뿐이지 실제로는 굉장히 간단한 BFS 문제이다. 입력은 모두 숫자로 주어지므로 단순 정수 기본 아이디어는 다음과 같다.

 

1. 변환 횟수를 저장할 int 타입의 dis 배열, 방문 여부를 저장할 boolean 타입의 visit 배열 선언

2. 연결 리스트 형태로 그래프를 저장하기 위해 list 선언

3. BFS는 a에서 시작 (문자 변환을 a부터 시작하기 때문)

4. BFS 종료 후, b를 방문하였다면 dis[b]를 출력. 방문하지 않았다면 -1을 출력

 

추가로, 입력되는 a와 b가 같다면 변환할 필요가 없으므로 그래프 정보를 모두 입력받고 0을 출력하고 종료하면 된다. 이외에 놓칠뻔한 점으로는 문제만 읽어보면 단방향 그래프라 느낄 수 있는데, 예제를 모두 확인하고 보니 이 문제는 양방향 그래프에서의 BFS 문제였다. 문제 본문에서는 양방향 그래프인 점이 잘 드러나지 않는 점이 조금 그렇다.

 

여담으로 PS를 한동안 안하니 이런 기본적인 BFS 문제 푸는것도 살짝 시간이 걸려버렸다. PS는 진짜 길게 쉬면 안되는듯..

 

코드

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
 
 
public class Main {
    public static ArrayList<Integer>[] list;
    public static boolean[] visit;
    public static int[] dis;
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine());
        int a = Integer.parseInt(st.nextToken());
        int b = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(bf.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        list = new ArrayList[n+1];
        visit = new boolean[n+1];
        dis = new int [n+1];
        for (int i = 1; i<=n; i++) {
            list[i] = new ArrayList<>();
        }
        for (int i=0; i<m; i++) {
            st = new StringTokenizer(bf.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            list[u].add(v);
            list[v].add(u);
        }
        if (a == b) {
            System.out.println(0);
            return;
        }
        dis[a] = 0;
        bfs(a);
        if (visit[b]) System.out.println(dis[b]);
        else System.out.println(-1);
    }
    public static void bfs(int n) {
        Queue<Integer> q = new LinkedList<>();
        visit[n] = true;
        q.add(n);
        while(! q.isEmpty()) {
            int poll = q.poll();
            for (int i: list[poll]) {
                if (! visit[i]) {
                    visit[i] = true;
                    dis[i] = dis[poll] + 1;
                    q.add(i);
                }
            }
        }
    }
}