숨바꼭질2(BJ_G4_12851)

1. 문제 링크

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

 

---

 

2. 나의 코드

메모리: 42696kb
시간: 252ms
코드 길이: 1776B
시간 복잡도 : O(V)
설명:
- 메모이제이션을 사용하여 최단경로로 동생을 잡을 수 있게 저장
- BFS를 사용

 

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

public class Main {

    static int N, K;
    static int resultTime, resultCnt;
    static int[] dp;
    static boolean flag;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        dp = new int[100001];
        Arrays.fill(dp, Integer.MAX_VALUE);

        if (N == K) {
            System.out.println(0);
            System.out.println(1);
        } else {
            bfs(N);
            System.out.println(dp[K]);
            System.out.println(resultCnt);
        }
    }

    public static void bfs(int n) {
        Queue<Integer> q = new LinkedList<>();
        q.offer(n);
        dp[n] = 0;

        while (!q.isEmpty()) {
            int now = q.poll();

            if (now == K) {
                resultCnt++;
            }

            if (isValid(now + 1) && dp[now + 1] >= dp[now] + 1) {
                q.offer(now + 1);
                dp[now + 1] = dp[now] + 1;
            }
            if (isValid(now - 1) && dp[now - 1] >= dp[now] + 1) {
                q.offer(now - 1);
                dp[now - 1] = dp[now] + 1;
            }
            if (isValid(now * 2) && dp[now * 2] >= dp[now] + 1) {
                q.offer(now * 2);
                dp[now * 2] = dp[now] + 1;
            }
        }

    }

    public static boolean isValid(int n) {
        return 0 <= n && n <= 100000;
    }
}

 

---

 

3. 정답 코드

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

public class Main {
	static int N, K;
	static int time[];
	static int move [] = new int []{1, -1, 2};
	static int cnt;
	
	static void find() {
		Queue<Integer> que = new ArrayDeque<>();
		
		que.add(N);

		if (N==K) {
			cnt++;
			return; // 수빈이와 동생의 위치가 같다면 cnt 1, 종료
		}
		
		// BFS
		while(!que.isEmpty()) {
			int now = que.poll();
			
			for (int i=0; i<3; i++) {
				int next;
				if (i==2) next = now * move[i]; // 순간이동
				else next = now + move[i]; // 걷기
				
				// next가 범위 밖이거나, 이미 방문한 지점인데 기존 소요 시간보다 오래 걸린다면 X
				if (next<0 || next>100_000 || (time[next] != 0 && time[next] < time[now]+1)) continue;
				time[next] = time[now]+1; // 소요 시간 저장
				que.add(next);
				
        if (next == K) cnt ++; // 동생을 찾은 경우
			}
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(bf.readLine());
		
		N = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		time = new int[100_001];
		
		find();
		System.out.println(time[K]); // 최단 소요 시간
		System.out.println(cnt); // 방법 가지수
	}
}

 

---

 

4. 배운 점

- 중복을 허용 시켜야 한다. 다만 최단 경로일 경우만!

- 너무 오랜만에 알고리즘을 풀었다.. 감을 다 잃었다.

- BFS와 DFS, 백트래킹에 대해서 다시 공부를 해야겠다.