[백준][자바] 1326 - 폴짝폴짝 - BFS(완전탐색)

📌 문제

백준 | 폴짝폴짝 | SILVER 2 | 완전탐

https://www.acmicpc.net/problem/1326

 

 

📌 문제 탐색하기

• 징검다리에 숫자 존재
• 징검다리에 쓰여 있는 수의 배수만큼 떨어져 있는 곳으로 감
• a번째 징검다리에서 b번째 징검다리로 이동
• 출력 : 최소 몇 번 점프를 하여 b번까지 가는지

 

 

 

📌 알고리즘

• ‘최소’ 의 점프를 구해야하므로, 완전탐색(DFS/BFS)를 사용할 예정
  • DP와 같은 경우에는 ‘누적’된 정보들을 바탕으로 풀어야하는데, 이전 상태값에 의존하는 것은 아니므로 DP로 하지 않아도 될 것이라 생각했다.
• 징검다리의 개수 N이 10,000까지 존재하므로 O(N^2) = 100,000,000 < 2초 가능

 

📌 코드 설계하기

1. N, A, B 입력받기
2. BFS를 통해
   1. 앞으로 가는 경우
   2. 뒤로 가는 경우
   → 2가지 방법으로 가능한 경우들을 Queue에 입력받도록 구현
3. (2 방법 모두 visited를 활용해서 이미 지나간 돌은 제외한다.)

 

 

📌 정답 코드

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

public class Main {
    static int n;
    static int[] stones;

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

        int answer = 1;

        n = Integer.parseInt(br.readLine());

        stones = new int[n+1];
        st = new StringTokenizer(br.readLine());

        for(int i = 1; i<n+1; i++){
            stones[i] = Integer.parseInt(st.nextToken());
        }

        String[] ab = br.readLine().split(" ");

        int a = Integer.parseInt(ab[0]);
        int b = Integer.parseInt(ab[1]);

        System.out.println(bfs(a,b));

    }

    public static int bfs(int start, int end){
        int[] visited = new int[n+1];

        visited[start] = 1;

        Queue<Frog> queue = new LinkedList<>();

        queue.offer(new Frog(start, 0));

        while(!queue.isEmpty()){
            Frog frog = queue.poll();

            if(frog.pos == end){
                return frog.cnt;
            }

            int jump = stones[frog.pos];

            //앞으로가는경우
            for(int i = frog.pos; i< n+1; i+= jump){
                if(visited[i] == 1){
                    continue;
                }
                visited[i] = 1;
                queue.offer(new Frog(i, frog.cnt+1));
            }

            //뒤로가는경우
            for(int i = frog.pos; i>=1; i-= jump){
                if(visited[i] == 1){
                    continue;
                }
                visited[i] = 1;
                queue.offer(new Frog(i, frog.cnt + 1));
            }

        }
        return -1;

    }
}

class Frog {
    int pos;
    int cnt;

    public Frog(int pos, int cnt){
        this.pos = pos;
        this.cnt = cnt;
    }
}

 

처음에 뭔가 '최소' 라는 키워드에 꽂혀서 BFS인것은 눈치를 챘으나.. 확연하게 문제 푸는 방식이 떠오르지 않아 당황했다.

또한 A B 우리 뇌리속에선 A가 먼저, B가 이후인데 이에 대한 정보도 문제에선 주어지지 않았으니 ..... (당황) 

앞으로는 문제 접근을 할 때 내 상상보단, '문제'에 집중을 해야겠다 😢👍