백준 5014

문제개요

문제 해석

1. 제약조건 존재(이동 불가 시 use the stairs 출력
2. 버튼에 따른 수행 조건이 따로 존재
3. 초기화 여부 체크
   3-1. static 으로 사용하고 있기 때문에 초기화를 했는지 여부를 체크하는게 가장 중요해보인다.

이 문제는 내가 풀면서 생각했던 것들도 주석으로 남겨뒀다.
항상 문제를 다 풀고 나면 주석을 삭제할까도 고민하지만 아직은 남기려고한다.
미래의 내가 이걸 보고 이런 생각을 통해서 문제의 결과를 도출했구나를 알 수 있게

package bfs_dfs;

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

public class Beakjoon5014 {
    static int limit , source, destination;

    static Map<Integer,Integer> table = new HashMap<>();
    static int[] visit ;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int[] tmp = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();

        //초기화
        limit = tmp[0] + 2;
        source = tmp[1];
        destination = tmp[2];
        table.put(0,tmp[3]);
        table.put(1,-tmp[4]);
        visit = new int[limit];
        int result = 0;

        if (source != destination) {
            result = BFS(source, destination);
        }

        System.out.println(result!= -1?result : "use the stairs");
    }
/*
* 해당 목적지를 도착하는 최솟값이 필요하다.
* 배열이 필요하다. -> 배열이 1개 필요 (방문 여부 체크하는 테이블 필요)
* 갯수 측정 필요 -> count 변수 하나 필요
*   초기화 여부 체크 필요
* 배열의 길이 벗어나는지 검증하는 검증 메서드 필요
* BFS 활용 -> 큐를 이용해야한다.
* 1번지부터 로직을 실행해야한다. -> +1 해줘야한다.
* */
    private static int BFS(int source, int destination) {
        Queue<Integer> q = new LinkedList<>();
        q.add(source);
        visit[source] = 1;
        while(!q.isEmpty()){
            int tmp = q.poll();


            for (int i = 0; i < 2; i++) {
                 int next =tmp + table.get(i);

                if (isValid(next)) {
                    q.add(next);
                    visit[next] = visit[tmp] + 1;
                }

                if (next == destination) {
                    return visit[tmp] ;
                }
            }
        }
        return -1;
    }
    private static boolean isValid(int num) {
        return num > 0 && num < limit && visit[num] == 0;
    }
}

코드 해석

간단하게 visit[] 배열을 만들어서 검증을 했다.
DFS를 사용할 때는 항상 boolean으로 visited[] 배열을 만들었던것 같은데 BFS를 이용할때는 뭔가 아직 그런 문제를 만난 적이 없다.

look-up 테이블을 작성할 때의 장점이 위의 코드에서 명확하게 들어나 있다.

            for (int i = 0; i < 2; i++) {
                 int next =tmp + table.get(i);

이곳은 원래라면 분기처리해야되서 if문이 지저분하게 많이 나와야한다.
언젠가부터 lookiup-table을 쓰고 저런 부분에서 코드를 줄이고 가독성도 높일 수 있었다.
이쯤 문제를 풀어보니 이제 BFS DFS에 대한 자신감이 슬슬 붙어가는것같다.