[Line] 2019 상반기 LINE 인턴 채용 코딩테스트

문제 링크

1. 문제 이해

구현 + BFS를 사용하여 최단시간을 구하는 문제

2. 문제 분석

1. 브라운이 특정 칸에 도달할 수 있는 시간: BFS로 탐색

2. 특정 시간에 코니가 도달한 칸에 브라운이 가서 잡을 수 있는지:

• 브라운은 2초 후에 제자리로 돌아올 수 있습니다.
  ex) 2 -> 1 -> 2

• 만약 코니가 11초에 x에 도착했을 때
  1, 3, 5, 7, 9, 11초 중 한 번이라도 브라운이 그 칸에 도착했다면 코니를 잡을 수 있습니다.
  

• 만약 코니가 10초에 x에 도착했다면
  0, 2, 4, 6, 8, 10초 중 한 번이라도 브라운이 그 칸에 도착했다면 잡을 수 있습니다.

• 따라서 도착 시간을 홀수, 짝수로 나누어서 확인해야 합니다.

3. 코드

public class Main {
    static boolean[][] visited = new boolean[200_001][2];
    static final int even = 0, odd = 1;
    static Queue<Integer> q = new LinkedList<>();

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int conyPosition = sc.nextInt();
        int brown = sc.nextInt();

        q.add(brown);
        visited[brown][even] = true;
        visited[brown][odd] = true;

        int time = 0;
        while(inRange(conyPosition)) {
            int timeRemainder = time%2;

            if(visited[conyPosition][timeRemainder]) {//끝
                System.out.println(time);
                return;
            }

            time++;
            conyPosition += time;
            updateNextBrown(q.size(), time);
        }
        
        System.out.println(-1);
    }

    public static void updateNextBrown(int size, int time) {
        for(int i = 0; i < size; i++) {
            int index = q.poll();

            int[] nextIndex = {index-1, index+1, index*2};
            int timeRemainder = time%2;

            for(int j = 0; j < 3; j++) {
              int now = nextIndex[j];
              if(inRange(now) && !visited[now][timeRemainder]) {
                  visited[now][timeRemainder] = true;
                  q.add(now);
              }
            }
        }
    }

    public static boolean inRange(int num) {
        if(0 <= num && num <= 200_000) {
            return true;
        } else {
            return false;
        }
    }
}