[백준 14496번 / java] 그대, 그머가 되어

문제

14496번: 그대, 그머가 되어

 

풀이

알고리즘을 굉장히 오랜만에 풀어서 감을 다 잃었다 ^^..

 

일단 어떤 알고리즘을 사용해야 하는지도 떠오르지 않아서

그냥 인접리스트를 만들고 재귀로 모든 경로를 돌려서 a->b가 가능한지 찾았다.

 

코드1

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class boj_14496 {
    static int[][] arr;
    static int b, ans = -1;
    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;

        st = new StringTokenizer(br.readLine());
        int a = Integer.parseInt(st.nextToken());
        b = Integer.parseInt(st.nextToken());

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

        arr = new int[N+1][M];
        int[] cnt = new int[N+1];
        Arrays.fill(cnt, 0);

        for(int i=0; i<M; i++){
            st = new StringTokenizer(br.readLine());
            int num1 = Integer.parseInt(st.nextToken());
            int num2 = Integer.parseInt(st.nextToken());
            arr[num1][cnt[num1]] = num2;
            cnt[num1]++;
        }
        select(a, 1);
        System.out.println(ans);
    }
    static void select(int num, int cnt){
        for(int i=0; i<arr[num].length; i++){
            int val = arr[num][i];
            if(val == b) {
                if(ans < cnt) ans = cnt;
                return;
            } else if(val == 0){
                return;
            }else select(val, cnt+1);
        }
    }
}

먼저 한 방향으로만 바꿀 수 있게 짰다.

코드2

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class boj_14496 {
    static int[][] arr1, arr2;
    static int a, b, ans = Integer.MAX_VALUE;
    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;

        st = new StringTokenizer(br.readLine());
        a = Integer.parseInt(st.nextToken());
        b = Integer.parseInt(st.nextToken());

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

        arr1 = new int[N+1][M+1];
        arr2 = new int[N+1][M+1];
        for(int i=0; i<N+1; i++){
            Arrays.fill(arr1[i], 0);
            Arrays.fill(arr2[i], 0);
        }


        int[] cnt1 = new int[N+1];
        int[] cnt2 = new int[N+1];
        Arrays.fill(cnt1, 0);
        Arrays.fill(cnt2, 0);

        for(int i=0; i<M; i++){
            st = new StringTokenizer(br.readLine());
            int num1 = Integer.parseInt(st.nextToken());
            int num2 = Integer.parseInt(st.nextToken());
            arr1[num1][cnt1[num1]] = num2;
            cnt1[num1]++;
            arr2[num2][cnt2[num2]] = num1;
            cnt2[num2]++;
        }
        select(arr1, a, 1);
        select(arr2, a, 1);
        System.out.println(ans);
    }
    static void select(int[][] arr, int num, int cnt){
        for(int i = 0; i< arr[num].length; i++){
            int val = arr[num][i];
            if(val == b) {
                ans = Math.min(ans, cnt);
                return;
            } else if(val == 0){
                return;
            }else select(arr, val, cnt+1);
        }
    }
}

예제 테스트코드가 틀려서 다시 두 방향 다 볼 수 있게 만들었지만 메모리 초과가 발생했다.

직접 예제를 만들어 다시 돌려보니 재귀함수쪽에서 stackoverflow가 발생했다.

 

양 방향 그래프에서 한 정점에서 다른 정점까지 탐색을 할 때, 순환이 발생하기 때문이었다.

따라서 한 가지 경로를 탐색하는 중이고, 이미 방문한 정점이라면 방문처리하여 순환을 막아야 한다.

 

(처음에 메모리 초과라길래 인접 노드 저장할 때 내가 리스트를 써서 그런가 하고 이차원 배열로 바꿔봤지만 그게 문제가 아니었던..)

정답 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class boj_14496 {
    static List<List<Integer>> graph;
    static boolean[] visited;
    static int a, b, N, M;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        a = Integer.parseInt(st.nextToken());
        b = Integer.parseInt(st.nextToken());

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

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

        for (int i = 0; i < M; i++) { //인접리스트 만들기
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            graph.get(a).add(b);
            graph.get(b).add(a);
        }

        System.out.println(solve(a));

    }

    static int solve(int start){
        PriorityQueue<Node> pq = new PriorityQueue<>();
        visited = new boolean[N+1];

        pq.add(new Node(start, 0));
        visited[start] = true;

        while(!pq.isEmpty()){
            Node node = pq.poll();

            //b를 찾으면 cost를 반환
            if(node.num == b)
                return node.cost;

            //b가 아니면 큐에서 뽑은 노드의 인접 노드 중 아직 방문하지 않은 노드를 큐에 넣음
            for(Integer next : graph.get(node.num)){
                if(!visited[next]){
                    visited[next] = true;
                    pq.add(new Node(next,node.cost+1));
                }
            }
        }
        return -1;
    }
    static class Node implements Comparable<Node>{
        int num;
        int cost;
        Node(int num, int cost){
            this.num = num;
            this.cost = cost;
        }

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

[문제 분석]

이 문제는 문자열 a를 b로 바꾸는 문제처럼 보이나, 노드 a에서 노드 b로 가기 위한 최단경로를 구하는 문제이다.

 

최단경로를 구하는 아이디어는 다음과 같다 :

a와 연결되어있는 노드들을 순차적으로 따라가다가 b를 발견하는 순간 지금까지 몇 개의 노드를 거쳤는지 리턴

순차적이라함은 a와 1만큼 떨어져있는 노드들 중 b가 있는지 확인 -> a와 2만큼 떨어져있는 노드들(즉, a와 1만큼 떨어져있는 노드들의 인접노드들. 단, 방문한 노드 제외) 중 b가 있는지 확인 -> ... 을 의미

 

[알고리즘]

아이디어를 구현하기 위해서는 큐를 사용하는 것이 적절해보인다.

 

[풀이 방법]

1. 인접 노드들의 정보가 주어졌으므로, 이들이 어떤 형태로 이어져있는지 저장할 인접 리스트를 만든다. 중첩 리스트에 인접 리스트 정보를 저장

2. 큐에 넣을 Node 클래스를 만듦

3. 방문 배열 boolean[] visited를 선언

4. 탐색 시작

1. 시작값(a)을 가진 노드를 큐에 넣고 방문처리
2. 큐가 빌 때까지 루프를 시작
   1. 큐에서 노드를 하나 꺼냄
   2. b인지 확인, b가 맞으면 거리를 반환
   3. b가 아니면 인접 노드를 모두 큐에 넣고 방문처리 (이미 방문한 노드 제외)
   4. 큐에 노드를 넣을 때 cost는 꺼낸 노드의 cost+1로 설정
3. 큐가 비고 탐색이 끝났지만 아직 b를 못 찾았다면 -1을 반환

[예제]

이해를 위해 그림 첨부

a=1, b=5인 경우 다음과 같이 인접 노드가 연결되어있다면 큐에 그림과 같이 노드가 삽입될 것이다.

 

1. 맨 처음에 a=1 즉 (1,0)이 큐에 삽입된다.

 

2. 큐에서 (1,0)을 꺼낸다. 1 != 5이므로 1과 인접한 2, 4를 노드로 만들어 다시 큐에 삽입한다. 이때 2, 4의 cost는 꺼낸 노드의 cost에 1을 더한 값으로 설정한다. -> 큐에 (2,1), (4,1) 삽입

 

3. 큐에서 (2,1)을 꺼낸다.  2 != 5이므로 2와 인접한 1, 3 중 이미 방문한 1을 제외하고 3만 노드로 만들어 다시 큐에 삽입한다. 이때 3의 cost는 꺼낸 노드의 cost에 1을 더한 값으로 설정한다. -> 큐에 (3,2) 삽입

 

...

이 과정을 반복하다가 b를 찾으면 그 cost를 반환하면 된다.

 

 

Note

1->5로 가는 경로가 여러가지고 비용도 2, 3, 4로 다양해서 브루트 포스로 모든 경로와 그 비용을 비교해서 min값을 찾아야되지 않을까? 생각했는데 이렇게 큐를 사용하면 b를 찾는 대로 가장 가까운 경로를 리턴할 수 있었다.