[BFS] 백준 1326번 폴짝폴짝 - JAVA

 

조금 응용된 BFS 문제이다.

이름은 귀엽지만, 문제는 귀엽지 않았다 ㅡ ㅡ

 

 

---

1. 출처

---

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

1326번: 폴짝폴짝

 

• N개의 돌이 주어지고, 돌 위에는 점프할 수 있는 X배수가 써져있음
• X*1, X*2, X*3... 이런식으로 1~N 돌 안에서 이동할 수 있음
• 목적지에 도착하기 위해 밟아야 하는 최소의 돌 수를 도출
• 도착할 수 없다면 -1

 

 

---

2. 설계

---

 

 

문제를 보면 출발지 < 도착지라는 보장이 없다.

때문에 우리는 출발지 > 도착지, 출발지 < 도착지, 출발지 == 도착지라는 3가지 케이스에 대해 따져봐야 한다.

 

아래 설계를 보면 알겠지만, 앞 뒤 모든 경로를 파악하기 때문에  출발지 > 도착지, 출발지 < 도착지 2가지 케이스는 BFS에서 따진다.

출발지 == 도착지인 경우는 출발지가 도착지이므로 답은 0으로 도출하고 끝나면 된다.

 

 

1) 점프 범위

우리는 돌에 적혀있는 배수만큼 앞 뒤로 움직일 수 있다. 한 방향으로만 움직이는 것이 아니라는 의미이다.

예제로 이해해보자면, 다음과 같다.

5
3 2 2 1 3
5 1

 

5번 돌을 밟고, -3개를 넘어 2번 돌로 갈 수 있다. ( 5 -> 2 )

5번 돌을 밟고 뒤로는 못간다.

 

2번 돌은 배수가 2이므로 1번 돌로 갈 수 없다.

2번 돌을 밟고 뒤로 2칸을 갈 수 있다. ( 2 -> 4 )

 

4번 돌은 배수가 1이므로 1번 돌로 갈 수 있다. ( 4 -> 1 ) --> 도착지 끝!

 

그리하여 5 -> 2 -> 4 -> 1로 3개의 돌을 밟고 도착지에 갈 수 있다.

 

 

이런 이해를 바탕으로 다음과 같은 로직으로 풀어나갈 수 있다.

//뒤로
for(int i=(N-cur.S)/jump[cur.S]; i>0; i--){
	if(cur.S+jump[cur.S]*i>0 && cur.S+jump[cur.S]*i<N+1 && !visited[cur.S+jump[cur.S]*i]){
		q.offer(new Loc(cur.S+jump[cur.S]*i, cur.step+1));
	}
}

 

뒤로는 현재 위치(S)에서 +방향으로 점프를 할 수 있는 배수만큼 for을 돌려준다.

만약 내 위치가 1번 돌이고 5번 돌까지 있다면, 5-1 = 4칸을 뒤로 이동할 수 있는 것이다.

1번 돌의 배수가 2라면, 4/2 = 2회 for을 돌게 된다.

그리하여 2*2 -> 2*1 순으로 for이 돌게 되는 것이다.

 

//앞으로
for(int i=(cur.S-1)/jump[cur.S]; i>0; i--){
	if(cur.S-jump[cur.S]*i>0 && cur.S-jump[cur.S]*i<N+1 && !visited[cur.S-jump[cur.S]*i]){
		q.offer(new Loc(cur.S-jump[cur.S]*i, cur.step+1));
	}
}

 

앞으로는 현재 위치(S)에서 -방향으로 점프를 할 수 있는 배수만큼 for을 돌려준다.

만약 내 위치가 3번 돌이라면, 3-1(내가 서있는 곳 제외) = 2칸 앞으로 이동할 수 있는 것이다.

 

 

2) 어떤 알고리즘을 쓸까?

위처럼 출발점에서 앞으로, 뒤로 움직이며 최소 밟게 되는 돌 수를 알아내면 되는 것이다.

그렇기에 DFS, BFS가 연상될 수 있다.

 

 

2-1) DFS

DFS는 시스템 스택을 쓰기 때문에 시간 초과가 난다.

또한 내 로직 상 뒤로 갈 수 있는 것을 모두 찾고 난 다음에야 앞으로 갈 수 있는 것을 고려하기 때문에 더 시간이 많이 걸렸을 것이다.

public static void DFS(int S, int step){
	if(((start<end) && (S>end)) || ((start>end) && (S<end))){
		return;
	}

	if(S==end){
		count = Math.min(count, step);
		return;
	}

	//뒤로
	for(int i=(N-S)/jump[S]; i>0; i--){
		if(S+jump[S]*i>0 && S+jump[S]*i<N+1 && !visited[S+jump[S]*i]){
			visited[S+jump[S]*i] = true;
			DFS(S+jump[S]*i, step+1);
			visited[S+jump[S]*i] = false;
		}
	}

	//앞으로
	for(int i=S/jump[S]; i>0; i--){
		if(S-jump[S]*i>0 && S-jump[S]*i<N+1 && !visited[S-jump[S]*i]){
			visited[S-jump[S]*i] = true;
			DFS(S-jump[S]*i, step+1);
			visited[S-jump[S]*i] = false;
		}
	}
}

 

 

2-2) BFS

반면 BFS는 시간초과가 나지 않는다.

왜냐하면 1개의 돌을 밟는 것을 전부 조사하고, 2개의 돌을 밟는 것을 조사하는 방향으로 점진적으로 나아가기 때문에 최소의 돌이 나오는 순간 그만둘 수 있다.

public static void BFS(){
	Queue<Loc> q = new LinkedList<>();
	boolean[] visited = new boolean[N+1];
        
	q.offer(new Loc(start,0));
	visited[start] = true;
        
	while(!q.isEmpty()){
		Loc cur = q.poll();
            
		if(cur.S==end){
			count = Math.min(count, cur.step);
			return;
		}

		//뒤로
		for(int i=(N-cur.S)/jump[cur.S]; i>0; i--){
			if(cur.S+jump[cur.S]*i>0 && cur.S+jump[cur.S]*i<N+1 && !visited[cur.S+jump[cur.S]*i]){
				q.offer(new Loc(cur.S+jump[cur.S]*i, cur.step+1));
			}
		}

		//앞으로
		for(int i=(cur.S-1)/jump[cur.S]; i>0; i--){
			if(cur.S-jump[cur.S]*i>0 && cur.S-jump[cur.S]*i<N+1 && !visited[cur.S-jump[cur.S]*i]){
				q.offer(new Loc(cur.S-jump[cur.S]*i, cur.step+1));
			}
		}
	}
}
public static class Loc implements Comparable<Loc>{
	int S;
	int step;
        
	public Loc(int S, int step){
		this.S = S;
		this.step = step;
	}

	@Override
	public int compareTo(Loc o){
		return this.step>o.step?1:-1;
	}
}

 

여기서 Comparable은 사용하지 않아도 통과된다. BFS는 너비우선탐색 기법이기 때문에 기본 1개의 돌을 밟는 것을 전부 조사하고, 2개의 돌을 밟는 것을 조사하는 방향으로 점진적으로 나아가기 때문이다.

 

 

 

---

3. 전체 코드

---

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

class Main {
    
    static int N;
    static int[] jump;
    static int start;
    static int end;
    static int count = Integer.MAX_VALUE;
    
    public static void main(String[] args) throws Exception {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

        String jumps = br.readLine();
        StringTokenizer st = new StringTokenizer(jumps," ");
        
        jump = new int[N+1];//1부터 시작
        for(int i=1; i<=N; i++){
            jump[i] = Integer.parseInt(st.nextToken());
        }

        String AToB = br.readLine();
        st = new StringTokenizer(AToB," ");

        start = Integer.parseInt(st.nextToken());
        end = Integer.parseInt(st.nextToken());

        //입력 끝

        if(start == end) System.out.println(0);
        else{
    
            BFS();
            
            if(count == Integer.MAX_VALUE) System.out.println(-1);
            else System.out.println(count);
        }
    }
    public static void BFS(){
        Queue<Loc> q = new LinkedList<>();
        boolean[] visited = new boolean[N+1];
        
        q.offer(new Loc(start,0));
        visited[start] = true;
        
        while(!q.isEmpty()){
            Loc cur = q.poll();
            
            if(cur.S==end){
                count = Math.min(count, cur.step);
                return;
            }

            //뒤로
            for(int i=(N-cur.S)/jump[cur.S]; i>0; i--){
                if(cur.S+jump[cur.S]*i>0 && cur.S+jump[cur.S]*i<N+1 && !visited[cur.S+jump[cur.S]*i]){
                    q.offer(new Loc(cur.S+jump[cur.S]*i, cur.step+1));
                }
            }

            //앞으로
            for(int i=(cur.S-1)/jump[cur.S]; i>0; i--){
                if(cur.S-jump[cur.S]*i>0 && cur.S-jump[cur.S]*i<N+1 && !visited[cur.S-jump[cur.S]*i]){
                    q.offer(new Loc(cur.S-jump[cur.S]*i, cur.step+1));
                }
            }
        }
    }
    public static class Loc implements Comparable<Loc>{
        int S;
        int step;
        
        public Loc(int S, int step){
            this.S = S;
            this.step = step;
        }

        @Override
        public int compareTo(Loc o){
            return this.step>o.step?1:-1;
        }
    }
}

 

 

 

내가 썼던 테스트케이스!

5
3 2 2 1 3
5 1

//답 3
// 5 -> 2 -> 4 -> 1