[구름톤 챌린지, Java] 11일차, 통증(2)(BFS)

문제 링크

구름LEVEL

---

접근 방법

이 문제에 핵심

1. 통증 수치가 존재하며, 통증 수치를 감소하는 2개의 도구가 주어집니다.

2. 2개의 도구는 각각 통증 수치를 감소하는 양이 다릅니다.

3. 통증 수치가 0이 될 때 도구를 최소로 사용하는 개수를 결과로 출력합니다.

4. 통증 수치가 0미만으로 내려가면 해당 도구는 사용할 수 없습니다.

5. 통증 수치를 0으로 만들 수 없다면 -1을 결과로 출력합니다.

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. N부터 시작해서 통증 수치를 줄어드는 과정을 BFS탐색으로 탐색합니다.

 

3. 통증 수치가 0에 도달할 때 최소로 사용한 도구의 개수를 결과로 출력합니다.

 

 

구현

 

통증 수치 N부터 시작해서 0이 될 때까지 BFS탐색을 통해 0에 도달하는 도구 사용 최소값을 탐색합니다.

 

 

예를 들어.

 

N = 9

 

A = 3

 

B = 5

 

 

 

0	1	2	3	4	5	6	7	8	9(N)
0	0	0	0	0	0	0	0	0	0

 

1번째 탐색.

 

0	1	2	3	4	5	6	7	8	9
0	0	0	0	1(9-5)	0	1(9-3)	0	0	0

 

2번째 탐색.

 

0	1	2	3	4	5	6	7	8	9
0	2(6-5)	0	2(6-3)	1(9-5)	0	1(9-3)	0	0	0

 

3번째 탐색.

 

0	1	2	3	4	5	6	7	8	9
3(3-3)	2(6-5)	0	2(6-3)	1(9-5)	0	1(9-3)	0	0	0

 

BFS탐색을 통해 통증 수치가 0이 되었을 때 최소 사용 도구는 3개입니다.

 

위와 같이 BFS탐색이 끝났을 때,

 

사용한 도구의 개수가 0개 : 도달하지 못함 → -1 결과로 출력

 

사용한 도구의 개수가 0보다 클 때 : 도달 가능! → 최소 개수 결과로 출력

 

예제입력 1.

1. 입력된 정보를 저장합니다.

 

N : 11

A : 2

 

B : 7

 

2. N부터 시작해서 통증 수치를 줄어드는 과정을 BFS탐색으로 탐색합니다.

 

 

0	1	2	3	4	5	6	7	8	9	10	11(N)
0	0	0	0	0	0	0	0	0	0	0	0

 

1번째 탐색.

 

0	1	2	3	4	5	6	7	8	9	10	11(N)
0	0	0	0	1(11-7)	0	0	0	0	1(11-2)	0	0

2번째 탐색.

0	1	2	3	4	5	6	7	8	9	10	11(N)
0	0	2(9-7)	0	1(11-7)	0	0	2(9-2)	0	1(11-2)	0	0

3번째 탐색.

0	1	2	3	4	5	6	7	8	9	10	11(N)
3(2-2)	0	2(9-7)	0	1(11-7)	3(7-2)	0	2(9-2)	0	1(11-2)	0	0

 

통증 수치 0 도착!!!

 

3. 통증 수치가 0에 도달할 때 최소로 사용한 도구의 개수를 결과로 출력합니다.

 

3번째 탐색에서 0으로 도착하였기 때문에 최소 사용 도구의 개수는 3개입니다.

 

 

3 을 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer을 통해 띄어쓰기 기준 입력값을 나누었습니다.
• PriorityQueue와 BFS을 통해서 통증 수치 0에 가장 먼저 도달하는 도구 사용 개수를 탐색합니다.
• 탐색이 종료된 뒤 최소 도구 사용 개수를 결과로 BufferedWriter에 저장합니다.
• BufferedWriter에 저장된 결과를 출력합니다.

 

결과코드

import java.io.*;
import java.util.*;
class Main {
    //통증 정보 관련 클래스
    static class Info implements Comparable<Info>{
        //pos : 통증 수치
        //cnt : 도구 사용 개수
        int pos, cnt;

        //생성자
        public Info(int pos, int cnt) {
            this.pos = pos;
            this.cnt = cnt;
        }

        //사용 도구 개수 기준 오름차순 정렬
        @Override
        public int compareTo(Info o) {
            return this.cnt - o.cnt;
        }
    }
    public static void main(String[] args) throws Exception {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        //입력값 저장
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        int[] items = new int[2];
        items[0] = Integer.parseInt(st.nextToken());
        items[1] = Integer.parseInt(st.nextToken());
        //도구 사용 개수 기준 오름차순 정렬하는 PriorityQueue 생성
        PriorityQueue<Info> pq = new PriorityQueue<>();
        //초기 N(최초 통증 수치) 정보 저장
        pq.add(new Info(N, 0));
        //결과값 변수
        int result = -1;
        //통증 수치 방문 여부 확인 배열
        boolean[] visited = new boolean[N+1];
        //BFS탐색 진행
        while(!pq.isEmpty()){
            Info cur = pq.poll();
            //통증 수치 0에 도달하였을 때
            if(cur.pos == 0){
                result = cur.cnt;	//최소 도구 사용 개수 결과에 반영
                break;
            }
            //도달할 수 있는 통증 수치 탐색
            for(int i=0;i<2;i++){
                int nextPos = cur.pos - items[i];
                //방문하지 않았으며, 통증 수치가 0이상일 때
                if(nextPos >= 0 && !visited[nextPos]){
                    //해당 통증수치 관련 정보 저장
                    pq.add(new Info(nextPos, cur.cnt+1));
                    //통증 수치 방문 확인
                    visited[nextPos] = true;
                }
            }
        }
        //최소 도구 사용 개수 BufferedWriter 저장
        bw.write(String.valueOf(result));
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
}

 

---

느낀 점

 

문제에 분류가 DP로 되어 있었지만, 저는 BFS를 통해서 풀이를 진행하였습니다.

 

문제를 푸는 방식은 고정된 사고가 아닌 다양한 사고의 중요성을 깨닫게 되었습니다.