[백준] 5014번 : 스타트링크

5014번: 스타트링크

---

[DFS]

이런 DFS문제를 전에 풀어본 것 같다. 철수와 영희가 각각 i, j에 있을 때 철수가 왼쪽(-1), 오른쪽(+1)로만 움직일 수 있을 때 몇 번만에 영희를 만날 수 있는가? 와 같은 문제. 다만 처음에 오답을 받았다. 아무래도 DFS는 최단 거리를 찾기엔 부적합한 면이 없지않아 있으니 말이다. 다시 말해, 특정한 정점에 처음 도착했는데, 그 때가 최소값이 아닐 수 있다는 말이다. 그래서 대부분 BFS로 풀으신 것 같다.

 

하지만 DFS로도 264ms를 받고 AC했다. 각 정점마다 최대 2번 방문할 수 있게 하였고, 그 때의 엘리베이터를 몇 번 탔는지에 대한 값과 기존에 저장되어있는 값을 비교해 더 적은 값을 저장하였다.

# Code </>

public class Main {

    static int F, S, G, U, D, result = 1000000000;
    static int[] floor, visit;

    static void DFS(int start, int count){

        visit[start]++;
        
        if(start == G){
            result = Math.min(result, count);
            return;
        }

        if(floor[start] > count){
            floor[start] = count++;

            int up = start + U;
            int down = start - D;

            if(up <= F && visit[up] < 2) DFS(up, count);
            if(down > 0 && visit[down] < 2) DFS(down, count);
        }
    }

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

        //F:정점개수 S:Start G:Goal U: Up D:Down
        F = Integer.parseInt(st.nextToken());
        S = Integer.parseInt(st.nextToken());
        G = Integer.parseInt(st.nextToken());
        U = Integer.parseInt(st.nextToken());
        D = Integer.parseInt(st.nextToken());

        floor = new int[F+1];
        visit = new int[F+1];
        Arrays.fill(floor, 1000000000);

        DFS(S, 0);

        System.out.println(result == 1000000000? "use the stairs":result);
    }
}