백준 - 1697번, 숨바꼭질(sol.java)

◎문제 링크

https://www.acmicpc.net/problem/1697

1697번: 숨바꼭질

---

◎문제 파악

수빈이의 이동 가능 type

1. -1칸

2. +1칸

3. *2칸

---

◎코드 구현

package project;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

public class Main{
    int older, younger;//언니와 동생의 위치
    Queue<Integer> q = new LinkedList<>();
    int[] map = new int[100001];
    
    Main(int older, int younger){
        this.older = older;
        this.younger = younger;
        q.add(older);
        map[older] = 1;
    }
    
    public static void main(String[] args) throws IOException{
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] tmp = (br.readLine()).split(" ");
        Main m = new Main(Integer.parseInt(tmp[0]), Integer.parseInt(tmp[1]));
        m.bfs();
    }
    
    public void bfs(){

        while(!q.isEmpty()){
                
            int now = q.poll();
            
            if(now==younger){
                System.out.print(map[now]-1);
                break;
            }
            
            Minus(now);
            Doouble(now);
            Plus(now);
            
        }
    }
    
    public void Doouble(int now){
        if(now<=50000 && map[now*2] == 0){
            q.add(now*2);
            map[now*2] = map[now]+1;
        }
    }
    
    public void Minus(int now){
        if(now !=0&& map[now-1] == 0){
            q.add(now-1);
            map[now-1] = map[now]+1;
        }
    }
    
    public void Plus(int now){
        if(now != 100000 && map[now+1] == 0){
            q.add(now+1);
            map[now+1] = map[now]+1;
        }
    }
    
}

---

◎다른 사람의 코드

 

이 문제는 나의 코드 풀이가 맞기는 했지만, 여러모로 비효율적인 풀이이 때문에 나의 풀이에 대한 설명은 넘기고 다른 사람이 어떻게 풀어갔는지에서 발전할 부분을 이야기하겠다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	
	private static int min = Integer.MAX_VALUE;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int N = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());
        
		//문제를 dfs로 접근하였다.
		dfs(N, K, 0);
		System.out.println(min);
	}
	
	private static void dfs(int N, int K, int C) {
    
        //수빈이의 위치가 동생의 위치보다 클 경우 수빈이는 
        //동생의 위치에 도달할때까지 -1로 밖에 움직이지 못한다.
		if (N >= K) {
			check(C + N - K);
			return;
		}
		check(C + K - N);
		
        //수빈이의 위치가 0일 경우 +1로 밖에 움직이지 못한다.
        if (N == 0) {
			N = 1;
			C++;
		}
        
        //alpha
		if (K % 2 == 0) {
			dfs(N, K / 2, C + 1);
		} else {
			dfs(N, K - 1, C + 1);
			dfs(N, K + 1, C + 1);
		}
	}
	
    //beta
	private static void check(int C) {
		if (min > C) {
			min = C;
		}
	}

}

첫번째 특징으로는 문제를 풀때, DFS를 사용하였다. DFS는 BFS와는 달리 값이 도달하여도 최소경로로 도달하였다는 보장이 되지 않는다. 하지만, BFS가 메모리를 많이 사용하고, 트리에서 도착해야하는 값이 깊이 있을때 최악의 성능을 보이는 단점을 DFS는 잘 커버한다.

 

위의 코드에서 beta부분이 DFS가 답에 도달해도 최소경로로 도달하였다는 보장이 없기 때문에 min값을 다시 확인해주는 부분이다,

 

또한, alpha부분에서 N을 두배하는 대신에 K를 홀수 짝수로 구분하여 2로 나눠줌으로서 N이 제한된 범위(100,000)를 넘지않으면서, 2배가 되는 효과를 내었다. N을 두배하는 방법을 사용하면, 제한된 범위를 넘었다가 돌아오는 경로를 DFS가 탐색할 수 있다. K를 홀수 짝수로 구분하는 일은 *2가 +1로 구성될 수 있는 연산이므로, *2를 할 수 있을 때마다 함으로서, 필요없는 +1연산 경로로 가는 것을 방지한다.

 

---

그래프 탐색 문제를 풀면서, BFS를 자주 활용하고 DFS는 거의 활용하지 않았는데, BFS가 불리한 문제를 처음 만나서 당황했다. 그래프의 특성을 문제를 풀기전에 확실히 생각하고 들어가야겠다.