[알고리즘] 백준 1697 숨바꼭질 -bfs, dfs- 자바 코틀린

www.acmicpc.net/problem/1697

1697번: 숨바꼭질

 

 

 

 

백준 dfs, bfs 단계별 풀기에 있는 1697번 숨바꼭질 문제입니다. 

 

총 1초가 걸리는 3가지 이동 방법이 있으며 누나가 동생에게 가장 빨리 도착하는 시간초를 구하는 문제입니다.

 

 

1. 길을 나타낼 1차원 배열 선언, 값은 그 지점까지 도착한 시간초를 담아놀 예정

2. 처음 수빈이 위치를 큐에 넣음

3. bfs 탐색 시작

4. 수빈이 위치가 동생 위치와 같다면 break

5. 3가지 방법에 대해 모두 이동할 수 있으면 이동 시켜줌, 이 때 map이 0(방문안한곳) 인 경우만 이동시켜줘야함. 큐잉이므로 처음에 해당 지점 도달한게 가장 빠른 경로이기 때문. 나중에 해당 지점 방문하는건 더 느림 

 

[Java]

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

public class Main {

    private static int N; //수빈이 위치
    private static int M; //동생 위치
    private static int[] map = new int[100001];


    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();
        bfs();
        System.out.println(map[M]);
    }

    static void bfs() {
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(N);
        while (!queue.isEmpty()) {
            N = queue.poll();
            if (N == M) {
                break;
            }
            if (N - 1 >= 0 && map[N - 1] == 0) {
                queue.offer(N - 1);
                map[N - 1] = map[N] + 1;
            }
            if (N + 1 <= 100000 && map[N + 1] == 0) {
                queue.offer(N + 1);
                map[N + 1] = map[N] + 1;
            }
            if (N * 2 <= 100000 && map[N * 2] == 0) {
                queue.offer(N * 2);
                map[N * 2] = map[N] + 1;
            }
        }
    }


}

 

 

 

[Kotlin]

import java.util.*

private var N: Int = 0 //수빈이 위치
private var M: Int = 0 //동생 위치
private val map = IntArray(100001)



fun main(args: Array<String>) {
    val sc = Scanner(System.`in`)
    N = sc.nextInt()
    M = sc.nextInt()
    bfs()
    println(map[M])
}

internal fun bfs() {
    val queue = LinkedList<Int>()
    queue.offer(N)
    while (!queue.isEmpty()) {
        N = queue.poll()
        if (N == M) {
            break
        }
        if (N - 1 >= 0 && map[N - 1] == 0) {
            queue.offer(N - 1)
            map[N - 1] = map[N] + 1
        }
        if (N + 1 <= 100000 && map[N + 1] == 0) {
            queue.offer(N + 1)
            map[N + 1] = map[N] + 1
        }
        if (N * 2 <= 100000 && map[N * 2] == 0) {
            queue.offer(N * 2)
            map[N * 2] = map[N] + 1
        }
    }
}

 

github.com/mtjin/algorithm_practice/tree/master/%EB%B0%B1%EC%A4%80%201697%20%EC%88%A8%EB%B0%94%EA%BC%AD%EC%A7%88

mtjin/algorithm_practice

 

 

댓글과 공감은 큰 힘이 됩니다. 

감사합니다 !!