본문 바로가기
PS/BOJ

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

by Nahwasa 2023. 5. 10.

목차

    문제 : 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;
        }
    }

     

    댓글