[백준] code.plus(BFS 알고리즘,JAVA)1963번, 소수 경로

문제 링크

1963번: 소수 경로

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

 

접근 방법

그래프 알고리즘이란?

각 정점과 연결하는 선분의 정보를 가지고 BFS(너비 우선 탐색), DFS(깊이 우선 탐색) .... 등을 이용하여 정점에서 다른 정점으로 가는 최소값, 최대값 등의 문제에서 출력하라는 결과를 구하는 알고리즘입니다.

 

BFS?

BFS(너비 우선 탐색)은 아래 그림처럼 시작 노드에 인접한 노드를 모두 탐색한 후 인접한 노드를 기준으로 다시 인접한 노드를 찾아내는 것을 반복하여 탐색합니다.

시작 노드 탐색이 끝나면 인접했던 노드를 시작 노드로 생각하고 다시 탐색합니다.

출처: https://ko.wikipedia.org/wiki/%EB%84%88%EB%B9%84_%EC%9A%B0%EC%84%A0_%ED%83%90%EC%83%89

더 자세한 내용은 아래 링크에 들어가서 확인해주시면 감사하겠습니다.

너비 우선 탐색 - 위키백과, 우리 모두의 백과사전

 

이 문제에 핵심은

1. 현재 숫자에서 목표 숫자까지 변경하는 최소 횟수를 결과로 출력한다.

2. 숫자를 변경할 때에는 각 자리에 숫자 1개씩 변경이 가능하다.

3. 범위는 1000 ~ 9999까지 존재하며 숫자는 소수인 값만 주어진다.

 

에라토스테네스의 체를 이용하여 1000 ~ 9999까지의 소수를 구합니다.

 

BFS탐색으로 각 자리의 숫자를 변경하며 가장 먼저 목표 숫자에 도달할 때에 변경 횟수를 결과로 출력하였습니다.

 

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전

 

 

예제입력 1.

TC1.

Cur : 1033

Goal : 8179

 

일의 자리 변경 : 1030, 1031, 1032, 1034.... 1039

십의 자리 변경 : 1003, 1013, 1023, 1043.... 1093

백의 자리 변경 : 1133, 1233, 1333, 1444.... 1933

천의 자리 변경 : 2033, 3033, 4033, 5033.... 6033

 

※자리가 변경되었을 때 소수인 것만 사용합니다.

위 변경을 반복중....

 

1033 -> 1733 -> 3733 -> 3739 -> 3779 -> 8779 -> 8179

 

6번의 변경 후 8179 도달!

 

결과로 6 출력

• BufferedReader를 사용하여 입력 값을 받았습니다.
• StringTokenizer을 이용하여 각 TC에 현재 숫자와 목표 숫자를 저장하였습니다.
• 에라토스테네스의 체를 이용하여 1000~9999까지의 소수인 값들을 구분하였습니다.
• 각 자리의 숫자를 변경을 BFS탐색으로 진행하여 목표 숫자에 도달하는지 탐색하는 bfs함수를 실행하였습니다.
• 도달 불가능시 "Impossible", 도달 시 최소 변경 횟수를 BufferedWriter에 저장합니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• bfs함수는 각 자리의 변경을 BFS 탐색으로 진행하는 함수입니다.
• bfs함수는 목표 숫자에 도달하면 최소 변경 횟수, 도달하지 못하면 -1을 반환합니다.

 

import java.util.*;
import java.io.*;

public class Main {
	//BFS에 Queue에 사용할 클래스
    static class changeNum{
        int num, count;
        public changeNum(int num, int count) {
            this.num = num;
            this.count = count;
        }
    }
    static boolean[] decimal = new boolean[10000];	//1000~9999 소수 확인 배열
    static public void  main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //입력값 처리하는 BufferedReader
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        //결과값 출력하는 BufferedWriter
        StringTokenizer st;
        int T = Integer.parseInt(br.readLine());
        //에라토스테네스의 체을 이용해서 1000~9999 범위의 소수 구하기
        for(int i=2;i<10000;i++){
            if(!decimal[i]){
                for(int j=i*2;j<10000;j+=i){
                    decimal[j] = true;
                }
            }
        }
        //TC에 대한 숫자들을 저장 및 BFS 탐색 수행
        for(int i=0;i<T;i++){
            st = new StringTokenizer(br.readLine()," ");
            int cur = Integer.parseInt(st.nextToken());
            int goal = Integer.parseInt(st.nextToken());
            int result = bfs(cur,goal);
            if(result == -1)	//불가능한 경우
                bw.write("Impossible\n");
            else		//해당 숫자 최소 변경했을 때
                bw.write(result + "\n");
        }
        bw.flush();	//결과 출력
        bw.close();
        br.close();
    }
    //숫자 변경하는 BFS 탐색하는 함수
    static int bfs(int start, int goal){
        Queue<changeNum> queue = new LinkedList<>();
        boolean[] visited = new boolean[10000];
        visited[start] = true;
        queue.add(new changeNum(start, 0));
        while(!queue.isEmpty()){
            changeNum cur = queue.poll();
            int num = cur.num;
            int count = cur.count;
            if(num==goal)	//목표 숫자로 변경되었을 때
                return count;

            //일의 자리 바꾸기
            int n = num/10 * 10;
            for(int i=0;i<10;i++){
                int temp = n + i;
                if(!decimal[temp] && !visited[temp]){
                    visited[temp] = true;
                    queue.add(new changeNum(temp,count+1));
                }
            }
            //십의 자리 바꾸기
            n = (num/100 * 100) + (num%10);
            for(int i=0;i<10;i++){
                int temp = n + i*10;
                if(!decimal[temp] && !visited[temp]){
                    visited[temp] = true;
                    queue.add(new changeNum(temp,count+1));
                }
            }
            //백의 자리 바꾸기
            n = (num/1000 * 1000) + (num%100);
            for(int i=0;i<10;i++){
                int temp = n + i*100;
                if(!decimal[temp] && !visited[temp]){
                    visited[temp] = true;
                    queue.add(new changeNum(temp,count+1));
                }
            }
            //천의 자리 바꾸기
            n = num%1000;
            for(int i=1;i<10;i++){
                int temp = n + i*1000;
                if(!decimal[temp] && !visited[temp]){
                    visited[temp] = true;
                    queue.add(new changeNum(temp,count+1));
                }
            }
        }
        return -1;		//목표 숫자 도달 불가능시
    }
}