[BFS] 백준 13549 Java

BFS 를 이용한 문제 풀이

13549번: 숨바꼭질 3

 

문제 조건 

  * 시간 제한 : 2초

  * 메모리 제한 : 512MB

 

  위 조건과 문제 상황을 고려하며 자료구조를 계획했다.

  1. 술래와 숨는 사람의 위치 N ,K 는 모두 0 ~ 100,000 의 범위이므로 int로 생성 -> 8bytes

  2. Queue에 넣기 위한 Node ( int x, int sec ) 를 필드만 고려했을 때 -> 개당 8bytes

  After. 0 ~ 100,000 번지의 방문 체크를 하기위해 boolean[100001] 생성 -> 1bit * 100,001 , 약 12KB

Try 1 ) Location * 2 , Location - 1 , Location + 1 을 순서로 목적지 K 와 비교하며 종료 or 새로운 노드 생성 및 큐에 추가

   최소 sec 를 구해야하기 때문에 자식 노드의 순서를 정할 때 sec 가 늘지 않는 Loc * 2를 맨 처음 넣었다.

 

   Loc -1 과 Loc + 1을 어떻게 할까 고민 중에 수가 작아지면 *2 도 고려할 수 있지만 커지면 *2를 고려할 수 있는 경우가 줄어든다는

   느낌이 와서 간단한 테스트 케이스를 통해 순서를 정했다.

 

  Test case ) 5 -> 8 로 가려면 ?

     1. 5 -> 4 -> 8         :  sec = 1       :      * 2 를 할 수 있는 경우가 생김

     2. 5 -> 6 -> 7 -> 8 : sec = 3       :      * 2 를 할 수 없음

 

      ▶ Problem ) 직접 만들어놓은 몇가지의 테스트 케이스는 통과하나 굉장히 오래걸린다.

          -> x == 1 일 때 자식 노드의 x 는 1*2, 1-1, 1+1 인데 2, 0, 2 이므로 같은 위치를 재방문하는 오류가 있었다. 

Try 2  - Clear ) 방문체크를 하는 Boolean 배열을 이용하여 재방문을 하지 않도록 한다.

  술래가 지나간 점을 모두 방문체크하여 재방문하지 않도록 한다.

 

 < 동작 과정 >

  1. 술래의 위치 N , 목표 위치 K 를 입력받는다.

  2. Node ( N , 0 ) 을 root 로 두고 큐에 넣는다.

  3. 큐에서 하나씩 꺼내며 *2, -1 , +1을 하였을 때 K와 같고 방문하지 않았다면 sec, sec+1, sec+1 을 리턴하고 

      같지 않다면 이동한 지점을 방문 체크하고 큐에 해당 지점과 sec / sec+1을 노드로 생성하여 큐에 넣는다.

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class boj_13549 {
    static int N,K;
    static Scanner sc = new Scanner(System.in);
    static boolean[] visit;
    static final int max = 100001; // visit 0 ~ 100000 까지
    static Queue<Node> queue = new LinkedList<>();
    public static void main(String[] args) {
        visit = new boolean[max];
        N = sc.nextInt();
        K = sc.nextInt();
        visit[N] = true;
        System.out.println(bfs(new Node(N,0)));
    }

    private static int bfs(Node root) {
        // X -1 , X +1 , 2 * X 3개의 자식 노드가 생길 수 있음.
        if ( root.x == K){return 0;}
        queue.add(root);

        while(!queue.isEmpty()){
            Node n = queue.poll();

//            System.out.println("X : " + n.x + " Sec : " + n.sec);
            // X * 2 를 했을 때 범위 내에 있을 시 visit 체크 & K와 비교 후 Return Or Queue add 결정
            if ( n.x*2 <= max){
                if (!visit[n.x*2]){
                    if ( n.x*2 == K) return n.sec;
                    else {
                        visit[n.x*2] = true;
                        queue.add(new Node(n.x*2,n.sec));
                    }
                }
            }

            // X - 1 를 했을 때 범위 내에 있을 시 visit 체크 & K와 비교 후 Return Or Queue add 결정
            if  (n.x>0){
                if (!visit[n.x-1]){
                    if (n.x-1 == K) return n.sec+1;
                    else {
                        visit[n.x -1] = true;
                        queue.add(new Node(n.x-1,n.sec+1));
                    }
                }
            }

            // X + 1 를 했을 때 범위 내에 있을 시 visit 체크 & K와 비교 후 Return Or Queue add 결정
            if ( n.x < max-1){
                if (!visit[n.x+1]){
                    if (n.x+1 == K) return n.sec+1;
                    else {
                        visit[n.x+1] = true;
                        queue.add(new Node(n.x+1,n.sec+1));
                    }
                }
            }

        }
        return -1;
    }
    static class Node{
        int x;
        int sec;
        Node(int newX, int newSec){
            this.x = newX;
            this.sec = newSec;
        }
    }
}

 

Review 

코드를 줄이기위해 방문체크와 노드의 x K 비교를 큐에서 꺼낸 후의 단계에서 진행하도록 해보았는데 

이렇게 하게되면 리프 노드에서 하나씩 노드를 더 큐에 추가하기 때문에 메모리를 많이 잡아먹었다.

메모리를 적게하기 위해 새로운 지점을 노드로 생성하여 큐에 추가하기 전 비교를 하도록 하였다.