[백준] no12851: 숨바꼭질 2 - BFS(중복 일부 허용) — 궁금하신 점이 있다면 댓글로 남겨주세요.(2023년~ 노션으로 이동)

728x90

문제

* X : 현재 숫자

* K : 목표 숫자

* 조건 : X-1 또는 X+1 또는 X*2 가능

* 출력 : 최소 도달 cnt와 최소 도달 방법 수

문제 링크 : https://www.acmicpc.net/problem/12851

원리

이 문제는 BFS의 중복을 일부 혀용해 주는 경우가 핵심

즉, 기본적으로 중복 방문은 허용하지 않되, 중간 루트에 같은 시간을 소요해서 같은 위치에 도착한 경우의 중복은 허용

풀이방법

* 1. BFS로 최소 도달 시간을 구함

* 2. 최소 도달 시간과 같은 시간에 도달하는 경우를 cnt

나의 코드

1. [실패] 첫 시도 : BFS로 최소시간 구하기는 성공. 최소 경로 개수 count 실패.

: Recur부분에서 무한 루프에 빠짐

     private static int X;
     private static int K;
     private static int sec;
     private static int cnt;
     private static boolean[] visited = new boolean[100001];
     
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        X = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        
        sec = 0;
        cnt = 0;

        BFS(); // 최소 시간 구하기

        visited = new boolean[100001];
        Recur(X);
        // BFS2();

        bw.write(""+sec+"\n");
        bw.write(""+cnt+"\n");

        bw.close();
    }

    /**
     * 최소 시간을 구하는 BFS
     */
    private static void BFS() {
        Deque<Check> dq = new ArrayDeque<>();
        dq.add(new Check(X,0));
        visited[X] = true;

        while(!dq.isEmpty()) {
            Check check = dq.poll();
            int now = check.Now;
            int nowSec = check.Sec;
            if(now==K) {
                sec = nowSec; // 가장 먼저 도달하는 check의 cnt는 가장 적다.
                break;
            }
            
            for(int i=0 ; i<3 ; i++) {
                if(i==0 && !visited[now-1]) {
                    dq.add(new Check(now-1, nowSec+1));
                    visited[now-1] = true;
                }
                else if(i==1 && !visited[now+1]) {
                    dq.add(new Check(now+1, nowSec+1));
                    visited[now+1] = true;
                }
                else if(i==2 && !visited[now*2]) {
                    dq.add(new Check(now*2, nowSec+1)); 
                    visited[now*2] = true;
                }
            }
        }
    }

    private static class Check {
        private int Now;
        private int Sec;

        public Check (int now, int sec) {
            this.Now = now;
            this.Sec = sec;
        }
    }

    private static void Recur (int now) {
        if(now==K) 
            cnt++;
        else {
            if(0<=now && now<=100000) {
                for(int i=0 ; i<3 ; i++) {
                    if(i==0 && now-1>=0 && !visited[now-1]) {
                        Recur(now-1);
                        visited[now-1] = true;
                    }
                    else if (i==1 && now+1<=0 && !visited[now+1]) {
                        Recur(now+1);
                        visited[now+1] = true;
                    } else if (i==2 && now*2<=0 && !visited[now*2]) {
                        Recur(now*2);
                        visited[now*2] = true;
                    }
                }
            }
        }
    }

2. [실패] BFS를 두번 사용한 방법으로, 두 번째 BFS의 객체는 각자의 visited[]를 갖도록 설정

: 통합 visited를 사용하자니, 중간만 경로가 겹치는 다른 루트가 count 되지않기 때문

private static int X;
     private static int K;
     private static int sec;
     private static int cnt;
     private static boolean[] visited = new boolean[100001];
     
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        X = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        
        sec = 0;
        cnt = 0;

        BFS(); // 최소 시간 구하기

        visited = new boolean[100001];
        BFS2();

        bw.write(""+sec+"\n");
        bw.write(""+cnt+"\n");

        bw.close();
    }

    /**
     * 최소 시간을 구하는 BFS
     */
    private static void BFS() {
        Deque<Check> dq = new ArrayDeque<>();
        dq.add(new Check(X,0));
        visited[X] = true;

        while(!dq.isEmpty()) {
            Check check = dq.poll();
            int now = check.Now;
            int nowSec = check.Sec;
            if(now==K) {
                sec = nowSec; // 가장 먼저 도달하는 check의 cnt는 가장 적다.
                break;
            }
            
            for(int i=0 ; i<3 ; i++) {
                if(i==0 && !visited[now-1]) {
                    dq.add(new Check(now-1, nowSec+1));
                    visited[now-1] = true;
                }
                else if(i==1 && !visited[now+1]) {
                    dq.add(new Check(now+1, nowSec+1));
                    visited[now+1] = true;
                }
                else if(i==2 && !visited[now*2]) {
                    dq.add(new Check(now*2, nowSec+1)); 
                    visited[now*2] = true;
                }
            }
        }
    }

    private static class Check {
        private int Now;
        private int Sec;

        public Check (int now, int sec) {
            this.Now = now;
            this.Sec = sec;
        }
    }

    private static void BFS2() {
        Deque<Check2> dq = new ArrayDeque<>();
        boolean[] visited2 = new boolean[100001];
        visited2[X] = true;
        dq.add(new Check2(X,0,visited2));


        while(!dq.isEmpty()) {
            Check2 check = dq.poll();
            int now = check.Now;
            int nowSec = check.Sec;
            if(now==K && nowSec==sec) {
                cnt++;
            }
            
            for(int i=0 ; i<3 ; i++) {
                if(i==0 && now-1>=0 && !check.Visited[now-1]) {
                    boolean[] nowVisited = Arrays.copyOf(check.Visited, check.Visited.length);
                    nowVisited[now-1] = true;
                    dq.add(new Check2(now-1, nowSec+1, nowVisited));
                }
                else if(i==1 && now+1<100001 && !check.Visited[now+1]) {
                    boolean[] nowVisited = Arrays.copyOf(check.Visited, check.Visited.length);
                    nowVisited[now+1] = true;
                    dq.add(new Check2(now+1, nowSec+1, nowVisited));
                }
                else if(i==2 && now*2<100001 && !check.Visited[now*2]) {
                    boolean[] nowVisited = Arrays.copyOf(check.Visited, check.Visited.length);
                    nowVisited[now*2] = true;
                    dq.add(new Check2(now*2, nowSec+1, nowVisited)); 
                }
            }
        }
    }

    private static class Check2 {
        private int Now;
        private int Sec;
        private boolean[] Visited;

        public Check2 (int now, int sec, boolean[] visited) {
            this.Now = now;
            this.Sec = sec;
            this.Visited = visited;
        }
    }

3. [성공] 사실상 레퍼런스를 이해한 후 따라친 코드

private static int X;

private static int K;

private static int sec = Integer.MAX_VALUE;

private static int cnt = 0;

private static int[] visited = new int[100001]; // 단순 방문체크가 아닌, 방문 했을 떄 시간을 비교하기 위해 int형으로 사용

public static void main(String[] args) throws IOException {

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

StringTokenizer st = new StringTokenizer(br.readLine(), " ");

X = Integer.parseInt(st.nextToken());

K = Integer.parseInt(st.nextToken());

// 만약 X가 K보다 크면, 최소루트는 -1을 반복하는 방법밖에 없음

if(X>=K) {

System.out.println(X-K + "\n" + 1);

return;

}

// X가 K보다 작은 경우

BFS();

bw.write(""+sec+"\n");

bw.write(""+cnt+"\n");

bw.close();

}

/**

* 최소 시간을 구하는 BFS

private static void BFS() {

Deque<Integer> dq = new ArrayDeque<>();

dq.add(X);

visited[X] = 1;

while(!dq.isEmpty()) {

int now = dq.poll();

// 현재 방문 시간이 최소시간보다 큰데 아직 도착을 못했으면, 이미 최소가 아닌거임

if(sec < visited[now]) return;

// 각 연산방식을 순차적으로 적용해 주기 위한 반복문

for(int i=0 ; i<3 ;i++) {

int next = 0;

if(i==0) next = now - 1;

else if(i==1) next = now + 1;

else next = now * 2;

if(next<0 || next> 100000) continue; // 범위를 벗어나면 제낌

if(next == K) {

sec = visited[now]; // 처음 K에 도달한 경우 최소시간이 대입되며, 그 이후는 이미 위에서 최소시간을 넘어가는 경우에서 걸러짐

cnt++; // 이후 같은 시간안에 도착하는 경우마다 cnt++;

}

// 만약 첫 방문이거나, 다른 경우랑 중복도착했더라도 같은 시간이 걸린 경우 (중복을 허용해 주어야 하는 경우)

if(visited[next] == 0 || visited[next] == visited[now] + 1) {

dq.add(next); // 다음 계산 해준다.

visited[next] = visited[now] + 1; // 다음 방문할 곳에 경과한 시간을 체크해 주며, 최소시간일 때로 유지된다.

}

레퍼런스 코드

참고 링크 : 뱀귤님의 블로그

static int N, K;

static int[] time = new int[100001];

static int minTime = 987654321;

static int count = 0;

public static void main(String[] args) throws Exception {

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

StringTokenizer st;

st = new StringTokenizer(br.readLine());

N = Integer.parseInt(st.nextToken());

K = Integer.parseInt(st.nextToken());

if (N >= K) {

System.out.println((N-K) + "\n1");

return;

}

bfs();

System.out.println(minTime + "\n" + count);

}

static void bfs() {

Queue<Integer> q = new LinkedList<Integer>();

q.add(N);

time[N] = 1;

while (!q.isEmpty()) {

int now = q.poll();

// now 방문 시간이 최소 시간보다 크면 뒤는 더 볼 필요 없음

if (minTime < time[now]) return;

for (int i=0; i<3; i++) {

int next;

if (i == 0) next = now + 1;

else if (i == 1) next = now - 1;

else next = now * 2;

if (next < 0 || next > 100000) continue;

if (next == K) {

minTime = time[now];

count++;

}

// 첫 방문이거나 (time[next] == 0)

// 이미 방문한 곳이어도 같은 시간에 방문했다면 (time[next] == time[now] + 1)

// 경우의 수에 추가될 수 있기 때문에 Queue 에 한번 더 넣어줌

if (time[next] == 0 || time[next] == time[now] + 1) {

q.add(next);

time[next] = time[now] + 1;

}

Chat GPT 코드

[실패] 시작부터 싸하긴 했지만.. 얘는 왜이렇게 자신감이 넘치는 걸까..?

문제 번호까지 알려줬지만 틀려주는 우리 쥐피티

import java.util.*;

public class Main {
    static int N, K, count = 0, time = Integer.MAX_VALUE;
    static boolean[] visited = new boolean[100001];

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

    public static void bfs() {
        Queue<Node> queue = new LinkedList<>();
        queue.add(new Node(N, 0));
        visited[N] = true;

        while(!queue.isEmpty()) {
            Node current = queue.poll();
            visited[current.position] = true;

            if(current.position == K) {
                time = current.time;
                count++;
                continue;
            }

            if(current.position - 1 >= 0 && !visited[current.position - 1]) {
                queue.add(new Node(current.position - 1, current.time + 1));
            }

            if(current.position + 1 <= 100000 && !visited[current.position + 1]) {
                queue.add(new Node(current.position + 1, current.time + 1));
            }

            if(current.position * 2 <= 100000 && !visited[current.position * 2]) {
                queue.add(new Node(current.position * 2, current.time + 1));
            }
        }
    }

    static class Node {
        int position;
        int time;

        public Node(int position, int time) {
            this.position = position;
            this.time = time;
        }
    }
}

728x90

저작자표시 비영리 변경금지 (새창열림)

'알고리즘 저장소 (일반방식과 나만의 풀이) > JAVA' 카테고리의 다른 글

[백준] no12865: 평범한 배낭 - DP (0)	2023.05.21
[백준] no1504: 특정한 최단 경로 - 다익스트라 (0)	2023.05.18
[백준] no9465: 스티커 (0)	2023.05.09
[백준] no1043: 거짓말 - 그래프 탐색 (2)	2023.05.06
[백준] no11053: 가장 긴 증가하는 부분 수열 - 최장 증가 부분 수열 (LIS) (0)	2023.05.05

문제

원리

풀이방법

나의 코드

레퍼런스 코드

Chat GPT 코드

'알고리즘 저장소 (일반방식과 나만의 풀이) > JAVA' 카테고리의 다른 글

티스토리툴바