[백준/Java] 1326번 : 폴짝폴짝

✏️ 문제 탐색

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

 

a번째 징검다리에서 b번째 징검다리까지 가는 데 최소 몇 번의 점프가 필요한지 구하는 문제이다.

 

개구리가 왼쪽, 오른쪽 방향 모두 움직일 수 있다는 것에 주의

처음에는 앞으로만 움직일 수 있다고 생각하고 다음과 같이 아이디어를 떠올렸다.

현재 위치에서 b번째 징검다리까지 갈 수 있는지 확인하는 과정을 반복하여 답을 구할 수 있다.

• 현재 숫자 > b까지의 거리
  • 1배 길이만큼 점프해도 b보다 멀리 가버리므로 b에 도달할 수 없다. 
  • 따라서 -1 출력
• 현재 숫자 <= b까지의 거리
  • (b까지의 거리/현재 숫자)만큼 점프 횟수를 count하고 현재 위치를 갱신하여 계속 비교
  • b에 다다랐다면 점프 횟수 출력

 

✏️ 구현 아이디어

14

3 5 2 6 4 3 3 7 6 1 5 4 6 5 

3 10

 

위와 같은 입력이 주어진 경우 3번째 징검다리(a)에서 10번째 징검다리(b)에 갈 수 있는 최단 경로를 구해보자.

 

방문 경로 : 3

현재 이동 가능한 곳 : 3 5 2 6 4 3 3 7 6 1 5 4 6 5 

 

현재 위치에서는 b로 점프할 수 없다.

점프 횟수를 하나 늘려 다시 탐색한다.

 

방문 경로 : 3->1

현재 이동 가능한 곳 : 3 5 2 6 4 3 3 7 6 1 5 4 6 5

 

먼저 1번째 징검다리로 왔다. 여기서는 b로 점프할 수 있다.

여기서 더 탐색하면 점프 횟수가 지금보다 같거나 많을 것이므로, 가장 빨리 찾은 경로가 최단거리가 된다.

따라서 최단거리는 2이다.

---

 

• depth를 하나씩 늘려가며 이동 가능한 모든 곳 중 b가 있는지 확인하는 과정을 반복한다.
• 가장 먼저 b를 찾았을 때가 최단 거리이므로 탐색을 종료한다.

✏️ 시간복잡도

이미 방문한 곳은 다시 방문하지 않으므로 시간 복잡도는 O(N)이다.

 

징검다리 개수 N (1<= N <=10,000)

쓰여있는 정수 K (K <= 10,000)

 

입력값 범위를 고려하면 최악의 경우 N*K = 1억 번의 연산이 필요한데 제한 시간은 2초이므로 구현 가능하다. 

✏️ 알고리즘

• 깊이(depth)를 활용해 최단 경로를 찾는 문제
• O(N)의 시간 복잡도를 가진 알고리즘

-> BFS가 적합

 

✏️ 코드 설계

1. 입력값 받기
2. bfs에 쓰일 자료구조 선언
   1. Queue: LinkedList<> 인접 노드(이동 가능한 징검다리 위치) 저장
   2. visited: boolean[] 방문 체크
   3. count: int[] 점프 횟수 저장 --> count[b]만 -1로 초기화
3. bfs 실행
   1. 큐에서 시작 위치를 넣고 방문 체크
   2. 큐가 빌때까지 작업 실행
      1. 꺼낸 위치가 b이면 탐색 종료
      2. 꺼낸 위치에서 이동 가능한 위치를 모두 큐에 넣고 점프 거리를 1 증가시킨 후 방문 체크 (이미 방문한 곳 제외)
4. count[b] 출력

✏️ 오답 노트

• 점프 횟수를 갱신하는 부분을 count[i]++;로 구현하여 틀림
• bfs에서 for문 탐색할 때 N을 포함시킴
• count[b]값을 -1로 초기화시키지 않음

✏️ 정답 코드

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

public class Main {
    static int N;
    static int[] arr, count;
    static boolean[] visited;
    static Queue<Integer> q;

    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;

        N = Integer.parseInt(br.readLine());
        arr = new int[N];

        st = new StringTokenizer(br.readLine());
        for(int i=0; i<N; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }

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

        q = new LinkedList<>();
        visited = new boolean[10000];
        count = new int[10000];
        count[b] = -1;
        
        bfs(a, b);
        System.out.println(count[b]);

    }

    static void bfs(int a, int b){

        q.offer(a);
        visited[a] = true;

        while(!q.isEmpty()){
            int now = q.poll();

            if(now == b)
                return;

            //오른쪽 탐색
            for(int i=now+arr[now]; i<N; i+=arr[now]){
                if(!visited[i]){
                    count[i] = count[now]+1;
                    q.offer(i);
                    visited[i] = true;
                }
            }
            //왼쪽 탐색
            for(int i=now-arr[now]; i>=0; i-=arr[now]){
                if(!visited[i]){
                    count[i] = count[now]+1;
                    q.offer(i);
                    visited[i] = true;
                }
            }
        }
    }
}

 

✏️ Note

• BFS : 깊이(depth)를 활용해 푸는 문제 (최단경로 문제), 큐로 구현
• DFS : 모든 경우를 하나하나 탐색해야 하는 완전탐색 문제 (순열 조합 문제), 재귀/백트래킹으로 구현
• 내가 떠올린 풀이 방법이 어떤 시간 복잡도를 가지는 지 한 번에 계산하기 어려웠다.
• 무조건 브루트 포스로 푸는 방법 먼저 떠올리게 되는데 좋은 습관인지 잘 모르겠다.
• BFS 알고리즘 문제인지 한 번에 파악하기 어려웠다.
• 이번 스터디를 통해 그래프 탐색에 익숙해져야겠다.
• BFS, DFS 시간 복잡도는 노드 개수 N, 간선 개수 E일 때 O(N+E)
• https://lordofkangs.tistory.com/630