백준 문제 풀이 - 1697

1697 숨바꼭질 문제

그냥 여담

알고리즘 공부를 시작한지 얼마 되지 않아서 문제를 보고 고민을 하였다.
어떤 방법으로 접근을 해야 할 지 몰랐기 때문이다.
무식하게 풀어 보려고 했는데 뭔가 효율적인건 없을까 생각을 하다가 밑에 알고리즘 분류를 보니
백트래킹 과 DFS , BFS 가 보여서 아차 하며 깨닫게 되었다.
이런 개념 조차 아직 제대로 잡히지 않은 나에게 첫 문제이다.

자바로 만든 백준 제출의 첫 경험

처음 완성을 하고 백준에 제출을 했다.
바로 틀렸습니다가 나왔다. 분명 로직이 틀린게 없다고 생각했고, 뭐가 문제일까 하고 한참 삽질을 했다.
그래서 방법을 바꿔서 풀었다.
그래도 오류가 났다. 분명히 결과값은 같은데… 원인 분석에 들어갔다.
문제는 아주 간단했다. 패키지로 알고리즘 문제들을 다 모아놨었는데 그 패키지 선언문이 문제였다.
해당 줄을 삭제하자 아까와는 다르게 채점중.. 이란 단어도 떳다 ㅠㅠ
덕분에 문제를 좀 더 효율적으로 풀게 되긴 하였다.

나중에 첫 제출했던 코드도 패키지를 빼자 채점이 제대로 되었는데, 시간초과가 떳다.
첫 제출했던 코드는 이미 방문했던 위치를 검사하지 않게 짰었는데, 그것 때문에 시간이 오래 걸린것 같다.

어쨋든 그리하여 지금은 제대로 잘 풀었다.

내가 푼 로직

조건에 맞는 위치만큼 배열을 생성한다.
방문하지 않았다는것을 알리기 위해 배열을 -1로 채운다.
큐에 시작위치를 넣고 초기화를 한다.
큐에서 꺼낸 위치가 목적지와 같을때까지 아래를 반복한다.
(배열에 접근하는 인자가 위치값이다)
이동할 위치가 조건내이고, 아직 방문하지 않았다면 현위치의 시간값 +1을 하여 해당 위치의 시간값에 넣는다.

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

/**
 * Created by sanghyoun on 2017. 4. 9..
 */
public class B1697 {
    public static void main(String[] args) {
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
             BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out))) {
            String[] input = br.readLine().split(" ");
            int start = Integer.parseInt(input[0]);
            int end = Integer.parseInt(input[1]);
            int ret = bfs(start,end);
            bw.write(Integer.toString(ret));
        } catch (Exception e) {
            e.printStackTrace();
        }
    }

    public static int bfs(int start, int end) {
        int[] time = new int[100001];
        Arrays.fill(time, -1);
        Queue<Integer> que = new LinkedList<Integer>();
        que.add(start);
        time[start] = 0;
        while (!que.isEmpty()) {
            int curLocation = que.remove();
            if (curLocation == end) {
                return time[curLocation];
            }
            if ((curLocation - 1 >= 0) && (time[curLocation - 1] == -1)) {
                time[curLocation - 1] = time[curLocation] + 1;
                que.add(curLocation - 1);
            }
            if ((curLocation + 1 <= 100000) && (time[curLocation + 1] == -1)) {
                time[curLocation + 1] = time[curLocation] + 1;
                que.add(curLocation + 1);
            }
            if ((curLocation * 2 <= 100000) && (time[curLocation * 2] == -1)) {
                time[curLocation * 2] = time[curLocation] + 1;
                que.add(curLocation * 2);
            }
        }
        return -1;
    }
}