[JAVA] 백준 1697. 숨바꼭질 (BFS) :: 로직/코드 - GODZ

안녕하세요 GODZ입니다.

오늘은 BFS를 이용한 문제를 풀어볼 예정입니다.

---

1. 문제

 

2. 입출력 예제

 

3. 접근

1. 각 위치를 하나의 노드라고 생각하고, 이동할 수 있는 위치(+1, -1, *2)에 대해 각각을 다음에 탐색할 노드라고 생각하면 BFS로 풀 수 있습니다.

2. 이전 BFS 문제들과는 달리 각 노드에 대한 연결관계를 설정하지 않아도 되기에 더 간단하게 풀 수 있습니다.

 

4. 로직

플로우 차트를 통해 보여드리겠습니다.

다음엔 더 깔끔한 플로우 차트를 만들겠습니다. 만들고 나니 깔끔하지는 않네요.

여기서 방문체크 및 이동 횟수를 저장할 자료구조를 배열과 해시맵을 통해 각각 구현을 해보았습니다.

 

• 다음 위치 N'를 Key로, 이동 횟수를 Value를 가지는 HashMap

• 다음 위치 N'를 Index로, 이동 횟수를 배열의 값으로 설정한 배열

두 자료구조의 차이는 아래 결과에서 보겠습니다!

 

5. 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.StringTokenizer;
 
public class Main {
    static int N;
    static int K;
    static int[] posArr;    // 방문 여부 및  이동횟수를 체크하기 위함
    static LinkedList<Integer> queue;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine().trim());
        
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        posArr = new int[100001];
        queue = new LinkedList<>();
        boolean isEnd = false;
        
        // 최초 위치는 이동횟수 1로 초기화
        posArr[N] = 1;
        queue.add(N);
        
        while(!queue.isEmpty()) {
            if(isEnd) {
                break;
            }
            int currPos = queue.poll();
            int nextPos = 0;
            
            for(int i = 0; i < 3; i++) {
                switch(i) {
                case 0 :
                    nextPos = currPos - 1;
                    break;
                case 1 :
                    nextPos = currPos + 1;
                    break;
                case 2 :
                    nextPos = currPos * 2;
                    break;
                }
                
                // 다음 좌표가 방문한 적이 없고, 유효 범위 안이라면
                if(isValidPos(nextPos) && posArr[nextPos] == 0) {
                    // 1. queue에 삽입
                    queue.add(nextPos);
                    
                    // 2. 방문 체크
                    posArr[nextPos] = posArr[currPos] + 1;
                    
                    if(nextPos == K) {
                        isEnd = true;
                        break;
                    }
                }
            }
        }
        System.out.println(posArr[K] - 1);
        
    }
 
    private static boolean isValidPos(int pos) {
        boolean res = false;
        if(pos >= 0 && pos <= 100000) {
            res = true;
        }
        return res;
    }
}
 

 

 

6. 결과

HashMap 사용

배열 사용

 

확실히 방문 체크에 대해 다른 자료구조보다 배열이 더 빠르고 메모리도 훨씬 적게 사용하네요!

앞으로는 저도 배열 위주로 좀 더 효율적인 코드를 짜야겠다고 느꼈습니다.

 

다들 열공하세요!