[백준 JAVA] 회귀한 프로그래머의 BFS 다시풀기

숨바꼭질

 

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

public class Main {
    public static int N, K;
    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());

        bfs();

    }
    public static void bfs(){
        Queue<Integer> q = new LinkedList<>();
        int[] visited = new int[200001];
        q.offer(N);
        visited[N] = 1;
        int cnt = 0;
        while(!q.isEmpty()){
            int size = q.size();
            for(int i = 0; i < size; i++){
                int cur = q.poll();
                if(cur == K) {
                    System.out.println(cnt);
                    return;
                }
                if(cur + 1 < 200001 && visited[cur + 1] == 0) {
                    visited[cur] = 1;
                    q.offer(cur + 1);
                }
                if(cur - 1 >= 0 && visited[cur - 1] == 0) {
                    visited[cur] = 1;
                    q.offer(cur - 1);
                }
                if(cur * 2 < 200001 && visited[cur * 2] == 0) {
                    visited[cur] = 1;
                    q.offer(cur * 2);
                }
            }
            cnt++;
        }
    }
}

 

숨바꼭질 4

시작점이 0일때나 시작점과 끝점이 같을 때 처리하는 반례 때문에 꽤나 애를 먹었다.

배열을 방문만 처리하는 배열과 이전노드를 저장하는 배열 두개를 쓸게 아니면 이 방법이 유일한것같다.

 

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

public class Main {
    public static int N, K, ans = 0;
    public static int[] visited = new int[100001];
    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());
        if(N == K){
            System.out.println(ans);
            System.out.println(K);
        } else{
            Arrays.fill(visited, -1);
            bfs();
        }

    }
    public static void bfs(){
        Queue<Integer> q = new LinkedList<>();
        q.offer(N);
        visited[N] = -2;
        while(!q.isEmpty()){
            int size = q.size();
            for(int i = 0; i < size; i++){
                int cur = q.poll();
                if(cur == K) {
                    System.out.println(ans);
                    route();
                    return;
                }
                if(cur + 1 < 100001 && visited[cur + 1] == -1) {
                    visited[cur + 1] = cur;
                    q.offer(cur + 1);
                }
                if(cur - 1 >= 0 && visited[cur - 1] == -1) {
                    visited[cur - 1] = cur;
                    q.offer(cur - 1);
                }
                if(cur * 2 < 100001 && visited[cur * 2] == -1) {
                    visited[cur * 2] = cur;
                    q.offer(cur * 2);
                }
            }
            ans++;
        }
    }

    public static void route() {
        Stack<Integer> st = new Stack<>();
        int cur = K;
        while(cur != -2){
            st.push(cur);
            cur = visited[cur];
        }
        StringBuilder sb = new StringBuilder();
        while(!st.isEmpty()){
            sb.append(st.pop()).append(' ');
        }
        System.out.println(sb);
    }
}

 

이모티콘

빠르게 풀었는데 37퍼에서 오류가 났다.

 

이유를 생각해보니 방문배열을 1차원으로 그냥 화면에 있는 이모티콘만 생각했을때 클립보드에 있는 이모티콘의 수도 같이 생각해야된다고 판단해서 2차원배열로 만들어주었다.

 

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

public class Main {
    public static int S;
    public static int[][] visited = new int[2001][2001];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        S = Integer.parseInt(br.readLine());

        bfs();

    }
    public static void bfs(){
        Queue<int []> q = new LinkedList<>();
        q.offer(new int[] {1, 1});
        visited[1][1] = 1;
        int cnt = 1;
        while(!q.isEmpty()){
            int size = q.size();
            for(int i = 0; i < size; i++){
                int cur[] = q.poll();
                if(cur[0] == S){
                    System.out.println(cnt);
                    return;
                }
                // 1.화면에 있는 이모티콘을 모두 복사해서 클립보드에 저장한다.
                if(cur[0] != cur[1]) {
                    q.offer(new int[]{cur[0], cur[0]});
                }
                // 2.클립보드에 있는 모든 이모티콘을 화면에 붙여넣기 한다.
                if(cur[0] + cur[1] <= 2000 && visited[cur[0] + cur[1]][cur[1]] == 0){
                    visited[cur[0] + cur[1]][cur[1]] = 1;
                    q.offer(new int[] {cur[0] + cur[1], cur[1]});
                }
                // 3.화면에 있는 이모티콘 중 하나를 삭제한다.
                if(cur[0] - 1 > 0 && visited[cur[0] - 1][cur[1]] == 0){
                    visited[cur[0] - 1][cur[1]] = 1;
                    q.offer(new int[] {cur[0] - 1, cur[1]});
                }
            }
            cnt++;
        }
    }
}

 

숨바꼭질 3

 

처음엔 단순 BFS 로 풀이했는데 반례가 존재할꺼같아 GPT 의 도움을 받아 다시 풀었다.

 

BFS 로 풀어도 이 문제가 풀리긴 하지만 좀 더 정확한 풀이를 위해선 0 - 1 BFS 로 풀었다.

 

간선이 0과 1밬에 존재하지 않는 최단거리 탐색 방법이다.

 

만약 0과 1 말고 다른 경우가 존재한다면 다익스트라로 푸는것이 맞는것같다.!

 

 

• 0-1 BFS (Deque)
  • 각 간선을 O(1) 로 처리 가능
  • 전체 복잡도: O(V + E)
  • 여기서는 정점 V=100,001, 간선은 최대 3V 정도 → O(3×10⁵) 수준
  • 실전에서 가장 빠름
• 다익스트라 (PriorityQueue)
  • 매 삽입/삭제가 O(log V)
  • 전체 복잡도: O(E log V) ≈ 3×10⁵ × log(10⁵)
  • log(10⁵) ≈ 17 → 연산량이 수백만 단위
  • 충분히 AC 나오지만 Deque보다 느림

 

 

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

public class Main {
    static final int MAX = 100000;
    public static int N, K;
    public static int[] dist;
    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());

        if(N >= K){
            System.out.println(N - K);
            return;
        }

        dist = new int[MAX + 1];
        Arrays.fill(dist, Integer.MAX_VALUE);

        bfs();
    }
    public static void bfs(){
        Deque<Integer> dq = new ArrayDeque<>();
        dist[N] = 0;
        dq.offer(N);

        while(!dq.isEmpty()){
            int x = dq.pollFirst();

            if(x == K){
                System.out.println(dist[x]);
                return;
            }

            int nx = x  * 2;
            if(nx <= MAX && dist[nx] > dist[x]) {
                dist[nx] = dist[x];
                dq.offerFirst(nx);
            }

            nx = x + 1;
            if(nx <= MAX && dist[nx] > dist[x] + 1) {
                dist[nx] = dist[x] + 1;
                dq.offerLast(nx);
            }

            nx = x - 1;
            if(nx >= 0 && dist[nx] > dist[x] + 1) {
                dist[nx] = dist[x] + 1;
                dq.offerLast(nx);
            }
        }

    }
}

 

 

알고스팟

 

도착지점까지 이동하려면 몇초가 걸리는지 계산하는 문제가 아닌 벽을 몇개를 부수면 갈 수 있는지 계산하는 문제

 

예전에 풀었던 벽부수고 이동하기랑 비슷해 보였다.

 

그 문제는 이차원 배열을 이용하여 벽을 부순횟수와 위치를 방문배열에 동시에 저장해야하는데 그런느낌이랑은 좀 달랐다.

 

왜냐하면 벽을 부수는 횟수는 정해지지 않았고 벽을 부순 횟수를 구하는게 중요한 문제이기 때문이다.

 

가장 쉽게 풀 수 있는 방법은 위치와 몇번 부쉈는지 계산하며 방을 이동한다. 아까와 비슷한 0 - 1 BFS 로 풀 수 있을꺼같다.

 

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

public class Main {
    public static int M, N;
    public static int[][] map, dist;
    public static int[] dr = {-1, 0, 1, 0};
    public static int[] dc = {0, 1, 0, -1};
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        M = Integer.parseInt(st.nextToken());
        N = Integer.parseInt(st.nextToken());
        map = new int[N][M];
        dist = new int[N][M];

        for(int i = 0; i < N; i++){
            String str = br.readLine();
            for(int j = 0; j < M; j++){
                map[i][j] = str.charAt(j) - '0';
            }
        }

        for(int i = 0; i < N; i++){
            Arrays.fill(dist[i], Integer.MAX_VALUE);
        }

        bfs();
    }
    public static void bfs(){
        Deque<int[]> dq = new ArrayDeque<>();
        dist[0][0] = 0;
        dq.offer(new int[] {0, 0});

        while(!dq.isEmpty()){
            int[] cur = dq.pollFirst();
            int r = cur[0];
            int c = cur[1];

            if(r == N - 1 && c == M - 1){
                System.out.println(dist[r][c]);
                return;
            }

            for(int d = 0; d < 4; d++){
                int nr = r + dr[d];
                int nc = c + dc[d];

                if(nr < 0 || nr >= N || nc < 0 || nc >= M) continue;

                if(map[nr][nc] == 0 && dist[nr][nc] > dist[r][c]) {
                    dist[nr][nc] = dist[r][c];
                    dq.offerFirst(new int[] {nr, nc});
                }

                if(map[nr][nc] == 1 && dist[nr][nc] > dist[r][c] + 1) {
                    dist[nr][nc] = dist[r][c] + 1;
                    dq.offerLast(new int[] {nr, nc});
                }
            }


        }

    }
}

 

이전에는 풀고나서 다른 블로그에서 더 잘 푼 사람이나 다른방법으로 푼게 있으면 보고 피드백을 했는데 요즘은 그냥 gpt 한테 물어보는게 더 정확하고 깔끔하게 푸는것같다.