[BOJ - JAVA] 11060 - 점프 점프 (DFS)

# 주소

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

11060번: 점프 점프

# 문제 

# 문제 해설 및 코드 리뷰

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    static int n,s;
    static int[] arr;
    static boolean[] visit;
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        arr = new int[n];
        visit = new boolean[n];
        for(int i = 0; i < n; i++)
            arr[i] = scan.nextInt();
        int s = Integer.MAX_VALUE;
        s = Math.min(s, dfs(0, 0));
        System.out.println(s);
    }
    static int dfs(int x, int cnt){
        visit[x] = true;
        Queue<Point> queue = new LinkedList<>();
        queue.offer(new Point(x, 0));
        while (!queue.isEmpty()) {
            Point now = queue.poll();
            if(now.x == n-1)
                return now.cnt;
            if(arr[now.x] == 0)
                continue;
            for(int i = 1; i <= arr[now.x]; i++){
                if(now.x + i < n && !visit[now.x + i]) {
                    visit[now.x + i] = true;
                    queue.offer(new Point(now.x + i, now.cnt + 1));
                }
            }
        }
        return -1;
    }
}
class Point{
    int x;
    int cnt;
    Point(int x, int cnt){
        this.x = x;
        this.cnt = cnt;
    }
}

하 3일동안 공부를 너무 못했습니다. 사연이 있는데...

어제는 MariaDB설치하다가 하루 다 날렸고 오늘은 이제 포맷까지 하고 잘 되서 STS설치하는데 이젠 여기서 또 막힙니다.

Eclipse MarketPlace 들어가서 Eclipse web developer 툴 다운받으려고 별 짓을 다했는데 검색하니까 자꾸 인터넷이 안된다고 끊기더라고요.

아니 네이버 잘만 들어가지고 유튜브 잘만 들어가지는데 왜 이게 안되죠?

그래서 구글링 싹다 동원하고 다 했는데도 안됩니다.

STS다 지우고 방화벽도 풀어보고 구글링도 해보고 다른 버전 설치해보고 해도 안되더라고요.

그래서 오늘 하루도 날렸습니다 ㅋㅋㅋㅋ

결국 포맷까지 하고 나니까 되네요.

진짜... 그냥 STS 문제인거.. 같기도 하고 뭔지 모르겠어서 시간도 얼마 없기도 하고 그냥 앞에 보이는 아무 dfs문제나 갖고와서 20분 만에 풀었습니다.

어려울줄 알았는데 쉽더라고요. 경험치가 1%도 안오른거보면 한 실버 2~3정도 될 것 같습니다.

 

Scanner scan = new Scanner(System.in);
    n = scan.nextInt();
    arr = new int[n];
    visit = new boolean[n];
    for(int i = 0; i < n; i++)
        arr[i] = scan.nextInt();
    int s = Integer.MAX_VALUE;
    s = Math.min(s,dfs(0, 0));
    System.out.println(s);
}

저는 일단 n을 받아와서 arr와 visit배열의 크기를 선언하고 for문을 통해 arr를 입력받았습니다.

그리고 s를 Integer.MAX_VALUE라고 저장하여 s보다 작은 bfs문을 풀이하려 했습니다.

근데 여기 문제는 사실 오류가 있습니다.

문제에서 정수 값만큼 이동한다고 했는데, 정수라면 음수도 포함하잖아요?

근데 음수값은 전혀 고려안하고 자연수만 넣고 돌려도 정답이 되는걸보면 문제 출제자가 정수라고 썼지만 사실상 자연수를 의도한 것 같습니다.

오타라고 하기 보다는 문제를 조금 수정해주셨음 좋겠네요 ㅎ.

어쨌든 bfs문 내부를 살펴봅시다.

visit[x] = true;
Queue<Point> queue = new LinkedList<>();
queue.offer(new Point(x, 0));
while (!queue.isEmpty()) {
    Point now = queue.poll();
    if(now.x == n-1)
        return now.cnt;
    if(arr[now.x] == 0)
        continue;
    for(int i = 1; i <= arr[now.x]; i++){
        if(now.x + i < n && !visit[now.x + i]) {
            visit[now.x + i] = true;
            queue.offer(new Point(now.x + i, now.cnt + 1));
        }
    }
}
return -1;

전 내부를 이렇게 짰습니다.

visit을 true로 일단 만들고 queue에 점을 삽입하여 인접해 있는 칸으로 이동하려 합니다.

근데 이 문제는 수직선 위를 움직이기 때문에 for문을 이용하여 해당하는 arr[x]의 크기 이하의 점을 선택해서 움직일 수 있게 해놓았습니다.

결국은 재귀문제라서 굳이 queue를 안쓰고 풀어도 되긴 하지만 bfs로 푸는게 전 훨씬더 깔끔하고 에러도 덜나더라고요.

n값이 커질수록 dfs문이 유리하지만 n값이 작다면 bfs문으로 풀어도 시간차이가 거의 안나기 때문에 웬만해선 bfs로 푸는 편입니다.

어쨌든,,

for(int i = 1; i <= arr[now.x]; i++){
    if(now.x + i < n && !visit[now.x + i]) {
        visit[now.x + i] = true;
        queue.offer(new Point(now.x + i, now.cnt + 1));
    }
}

다른 우선 탐색의 문제와 다르게 이 부분이 이 문제의 핵심입니다.

for문을 이용하여 arr의 크기 이하의 점들에 대해 now.x + i값이 n을 벗어나지 않는 범위 선에서 방문하지 않은 인덱스에 대해 queue에 점을 삽입하는 것을 알 수 있는데요.

처음에 이거 5분만에 다 하고 정답 제출하려하니 정답이 -1이 나와서 아 왜그러지 하고 있었는데 자세히 보니 queue.offer(new Point할 때 (now.x + i, now.cnt + 1)이라 해야하는데 (now.x + i, cnt + 1)이라고 해서 계~속 틀렸다 하더라고요 ㅋㅋㅋ.

아무래도 한글이 아니고 영어다 보니 실수한 부분에 대해 빨리 찾는게 어렵긴 합니다.

이 while문이 다 끝나고 났다는 것은 사실상 목표 지점에 도달하지 못했다는 것을 의미합니다.

그래서 return -1을 해주게 되면, return되지 못했던 dfs문이 마침내 -1로 리턴되어 도착하지 못했을 때 정답인 -1이 출력되게 할 수 있습니다.

class Point{
    int x;
    int cnt;
    Point(int x, int cnt){
        this.x = x;
        this.cnt = cnt;
    }
}

전 클래스를 x와 cnt 2개의 인자를 써서 구성했습니다.

감사합니다.