[백준(baekjoon) 1463] 1로 만들기 / BFS
2018. 6. 8. 15:39ㆍAlgorithm
반응형
문제
정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.
- X가 3으로 나누어 떨어지면, 3으로 나눈다.
- X가 2로 나누어 떨어지면, 2로 나눈다.
- 1을 뺀다.
정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최소값을 출력하시오.
해결
문제가 쉬운 편이지만, 자주 쓰이는 간단한 원리이니만큼 정리를 해보고, memorization 유무에 따른 시간 비교를 해보았다.
알고리즘
BFS 방식으로 해보았다.
트리 구조로 정리하자면 아래와 같다.
Queue를 만들어 입력값을 우선 넣는다.(시작점)Queue안의 원소들은 하나씩pop되어 문제에 정의된 1~3번 과정을 거쳐Queue에 삽입된다.
- 일단 가능한 경우의 수를 모두 넣어두는 것!
- 1
10 % 3 == 1과 같이 조건에 맞지 않는 경우에는 삽입되지 않는다. - 2
3과 같이 이미 나왔던 수의 경우에는 아무것도 하지 않는다. (앞서 나온 원소와 같은 결과가 나올 것이지만 자신이 더 늦기 때문에 할 필요가 없다.)
Queue원소가 비거나1이 나올 때 까지 해당 과정을 반복한다.
- 3
1이 나오는 경우 해당depth = count를 출력한다. - 입력 값이 1이상의 자연수이므로, 무조건 실행되는
n - 1작업이 있기 때문에 언젠가는1이 반드시 나온다. 이 경우,count = n-1이 될 것.
- 3
구현
두가지 방식으로 구현해보았는데, 결과적으로 큰 차이는 없었다.
공통적인 것
Queue에 원소들을 저장한다는 것n+1크기의boolean배열에 방문 원소를 체크한다는 것
다른 것
count 때문에 좀 다르다.
1. class를 사용해 원소 별로 num, count을 저장해두는 방식
- 원소의
count에 바로 접근할 수 있기 때문에 따로depth를 확인할 필요가 없다. - 즉, queue는 하나만 있으면 된다.
1.import java.util.*;
2.
3.public class Main {
4. static Scanner sc;
5. static boolean[] check;
6. public static void main (String[] args) {
7. sc = new Scanner(System.in);
8. int n = sc.nextInt();
9.
10. Queue<Node> queue = new LinkedList<>();
11. check = new boolean[n+1];
12. queue.add(new Node(n, 0));
13.
14. while (!queue.isEmpty()) {
15. Node node = queue.remove();
16. int num = node.num;
17. if (num == 1) {
18. System.out.println(node.count);
19. break;
20. }
21. if (num > 1 && !check[num]) {
22. check[num] = true;
23. int count = node.count + 1;
24. if (num % 3 == 0) queue.add(new Node(num / 3, count));
25. if (num % 2 == 0) queue.add(new Node(num / 2, count));
26. queue.add(new Node(num - 1, count));
27. }
28. }
29. }
30.
31. static class Node {
32. int num;
33. int count;
34.
35. public Node (int num, int count) {
36. this.num = num;
37. this.count = count;
38. }
39. }
40.}
2. Queue 2개를 사용해 depth를 구분하여 count를 알아내는 방식
count는 main 지역변수로 선언해두고, depth 구분을 위하여 현재, 다음 Queue 두개를 생성한다.
- 현재
depth의Queue가 없어질 때 까지 원소들을 하나씩 꺼내 작업한다. - 새로운 수들은 다음
depth이므로after Queue에 저장해둔다. before Queue(= 현재depth)가 끝났을 경우
count를1늘린다.before = after가 된다.after은 새로 빈Queue가 된다.
1.import java.util.*;
2.
3.public class Main {
4. static Scanner sc;
5. static boolean[] check;
6. public static void main (String[] args) {
7. sc = new Scanner(System.in);
8. int n = sc.nextInt();
9.
10. Queue<Integer> before = new LinkedList<>();
11. Queue<Integer> after = new LinkedList<>();
12. check = new boolean[n+1];
13. int count = 0;
14. before.add(n);
15.
16. while (!before.isEmpty()) {
17. int num = before.remove();
18. if (num == 1) {
19. System.out.println(count);
20. break;
21. }
22. if (num > 1 && !check[num]) {
23. check[num] = true;
24. if (num % 3 == 0) after.add(num / 3);
25. if (num % 2 == 0) after.add(num / 2);
26. after.add(num - 1);
27. }
28.
29. if (before.isEmpty()) {
30. before = after;
31. after = new LinkedList<>();
32. count++;
33. }
34. }
35. }
36.}
결과
결론적으로 두가지 모두 큰 차이는 없었다. (아래 4, 5번)
그리고 궁금해서 이것저것 시도해본 코드들
위에서 부터 1~5라고 번호를 매기겠다.
- 1번 구현방법에서 방문
check없앤 경우
class.[변수명]형태로 모두 접근count계속 1씩 늘려줌
1.// 변경된 코드 1번 구현방법 21~27 부분
2.if (node.num > 1) {
3. if (node.num % 3 == 0) queue.add(new Node(node.num / 3, node.count + 1));
4. if (node.num % 2 == 0) queue.add(new Node(node.num / 2, node.count + 1));
5. queue.add(new Node(node.num - 1, node.count + 1));
6.}
- 1번 구현방법에서 방문
check없앤 경우
class.num으로 접근count변수 선언 후 연산 작업 한번만 처리
1.// 변경된 코드 1번 구현방법 21~27 부분
2.if (node.num > 1) {
3. int count = node.count + 1;
4. if (node.num % 3 == 0) queue.add(new Node(node.num / 3, count));
5. if (node.num % 2 == 0) queue.add(new Node(node.num / 2, count));
6. queue.add(new Node(node.num - 1, count));
7.}
- 1번 구현방법에서 방문
check없앤 경우 - 1번 구현방법
- 2번 구현방법
TODO
DP문제로도 풀 수 있다고 하는데, 아직 DP Top-Down과 Bottom-Up에 익숙치 않기 때문에 쉬운 문제(= 이 문제)로 연습을 먼저 해보자.
1463 DP Bottom-Up으로 풀기
1463 DP Top-Down으로 풀기
반응형