백준 14496번 그대, 그머가 되어 (java)

[Silver II] 그대, 그머가 되어 - 14496

문제 링크

성능 요약

메모리: 20844 KB, 시간: 180 ms

분류

너비 우선 탐색, 그래프 이론, 그래프 탐색

제출 일자

2024년 8월 16일 16:02:13

문제 설명

선린에 합격한 대호에게는 큰 고민이 있다. 대호는 중학교 3년 내내 공부만 했기 때문에, 요즘 학생들이 사용하는 ‘야민정음’에 대해서는 문외한이다. 친구들의 대화에 끼고 싶은 대호는 야민정음을 공부하기로 했다.

야민정음이란, 비슷한 모양의 글자를 원래 문자 대신에 사용하는 것을 일컫는다. 예를 들어, ‘그대’는 ‘그머’로, ‘팔도비빔면’은 ‘괄도네넴댼’으로, ‘식용유’는 ‘식용윾’으로, ‘대호’는 ‘머호’로 바꿀 수 있다. 아무 문자나 치환할 수 있는 건 아니며 치환이 가능한 몇 개의 문자들이 정해져있다.

예를 들어보자. (a, b), (a, c), (b, d), (c, d)가 주어지는 경우, a를 d로 바꾸는 방법은 a-b-d, a-c-d로 2개가 있다. (a, b), (b, c), (a, c)가 주어지는 경우, a를 c로 바꾸는 방법은 a-b-c, a-c의 2개가 있다. 하지만 이 경우에는 치환횟수에 차이가 생기게 된다.

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

프로그램 작성의 편의를 위해, 머호가 공부하는 모든 문자는 자연수로 표현되어 주어진다.

입력

첫째 줄에 머호가 바꾸려 하는 문자 a와 b가 주어진다. 둘째 줄에 전체 문자의 수 N과 치환 가능한 문자쌍의 수 M이 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ M ≤ 10,000) 이후 M개의 줄에 걸쳐 치환 가능한 문자쌍이 주어진다. 모든 문자는 N이하의 자연수로 표현된다.

출력

a를 b로 바꾸기 위해 필요한 최소 치환 횟수를 출력한다. 치환이 불가능한 경우는 –1을 출력한다.

풀이

간단한 bfs 문제이나 결함이 좀 많다.

 

1. 양방향 간선임을 문제를 읽고 알기 힘듦

2. 출발 지점과 시작 지점이 같고, a -> b로 향하는 간선이 존재할 때 0을 출력해야 할지 1을 출력해야 할지 알 수 없음

3. 출발 지점과 시작 지점이 같고, a -> b로 향하는 간선이 존재하지 않을 때 -1을 출력해야 할지 0을 출력해야 할지 알 수 없음.

 

출발 지점과 시작 지점이 같을 때 무조건 0을 출력하게 해주면 정답 처리가 된다.

전체 코드

public class Main {

    static int start,end, N,M,cnt = -1;
    static boolean visited[];
    static List<ArrayList<int []>> edge = new ArrayList<>();


    public static void main(String args[])throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        start = Integer.parseInt(st.nextToken());
        end = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        for(int i = 0 ;i<=N;i++){
            edge.add(new ArrayList<int []>());
        }

        visited = new boolean[N+1];

        for(int  i = 1 ;i<=M;i++){
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            edge.get(a).add(new int[]{b, 0});
            edge.get(b).add(new int[]{a, 0});

        }

        if(start == end){
            bw.write("0");
            bw.flush();
            return;
        }

        bfs();

        bw.write(String.valueOf(cnt));
        bw.flush();

    }

    public static void bfs(){

        ArrayList<int[]> ed = new ArrayList<>();

        ed.add(new int[] {start,0});

        visited[start] = true;

        while (!ed.isEmpty()){
            for(int  i = 0 ;i<edge.get(ed.get(0)[0]).size();i++){
                int k = edge.get(ed.get(0)[0]).get(i)[0];

                if(k == end){
                    cnt = ed.get(0)[1] + 1;
                    return;
                }

                if(!visited[k]){
                    visited[k] = true;
                    ed.add(new int[] {k,ed.get(0)[1]+1});
                }
            }
            ed.remove(0);
        }
    }
}