[자바] 백준 15558 - 점프 게임 (java)

목차

문제 : boj15558

 

 

필요 알고리즘

• BFS (너비 우선 탐색)
  
  • BFS로 풀 수 있는 문제이다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

 

풀이

  혹시 BFS에 대해 모른다면 '이 글'을 참고해보자. 최단거리를 찾는게 아닌데 BFS를 사용하는 이유는, '1초에 한 칸씩 각 줄의 첫 칸이 사라진다' 라는 부분에서 초가 결국 거리라고 생각하면 편하게 처리할 수 있기 때문이다.

 

  결국 그냥 동일한 라인의 +1지점, -1지점, 다른 라인의 +k지점을 이동하면서 N보다 큰 위치에 도착할 수 있느냐 묻는 문제이다. 여기서 사라진 칸에 도착하지 않기 위해 BFS로 '초'를 기록하는 셈이다.(참고로 -1지점으로 갈 때만 확인하면 된다.). 라인 교체의 경우 0을 좌측, 1을 우측 라인이라 설정하면 '1-현재라인번호 = 다른 라인 번호'가 되므로 편하다. 그리고 초기 배열 크기를 n+1+k로 해둔 이유는 그냥 별도로 if문으로 넘어갔는지 체크하기 귀찮았기 때문이다.

while (!q.isEmpty()) {
    SangGun cur = q.poll();
    if (cur.idx >= n) {	// n 이상의 지점 도착 시 '1' 출력하고 종료
        System.out.println(1);
        return;
    }

	// 동일 라인 +1지점 가기
    if (!arr[cur.line][cur.idx+1]) {	
        arr[cur.line][cur.idx+1] = true;
        q.add(new SangGun(cur.line, cur.idx+1, cur.limit+1));
    }

	// 동일 라인 -1지점 가기. 이 때 cur.limit이 지나간 '초'에 해당한다.
    if (cur.idx-1 > cur.limit && !arr[cur.line][cur.idx-1]) {
        arr[cur.line][cur.idx-1] = true;
        q.add(new SangGun(cur.line, cur.idx-1, cur.limit+1));
    }

	// 다른 라인 +k지점 가기
    if (!arr[1-cur.line][cur.idx+k]) {
        arr[1-cur.line][cur.idx+k] = true;
        q.add(new SangGun(1-cur.line, cur.idx+k, cur.limit+1));
    }
}

  

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    private void solution() throws Exception {
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());

        boolean[][] arr = new boolean[2][n+1+k];

        for (int i = 0; i < 2; i++) {
            String tmp = br.readLine();
            for (int j = 0; j < n; j++) {
                if (tmp.charAt(j) == '0')
                    arr[i][j] = true;
            }
        }

        if (arr[0][0]) {
            System.out.println(0);
            return;
        }

        Queue<SangGun> q = new ArrayDeque<>();
        q.add(new SangGun(0, 0, 0));
        arr[0][0] = false;

        while (!q.isEmpty()) {
            SangGun cur = q.poll();
            if (cur.idx >= n) {
                System.out.println(1);
                return;
            }

            if (!arr[cur.line][cur.idx+1]) {
                arr[cur.line][cur.idx+1] = true;
                q.add(new SangGun(cur.line, cur.idx+1, cur.limit+1));
            }

            if (cur.idx-1 > cur.limit && !arr[cur.line][cur.idx-1]) {
                arr[cur.line][cur.idx-1] = true;
                q.add(new SangGun(cur.line, cur.idx-1, cur.limit+1));
            }

            if (!arr[1-cur.line][cur.idx+k]) {
                arr[1-cur.line][cur.idx+k] = true;
                q.add(new SangGun(1-cur.line, cur.idx+k, cur.limit+1));
            }
        }

        System.out.println(0);
    }
}

class SangGun {
    int line, idx, limit;
    public SangGun(int line, int idx, int limit) {
        this.line = line;
        this.idx = idx;
        this.limit = limit;
    }
}