백준 1697번 숨바꼭질

문제

나의 풀이

import java.util.*;

public class Main {
    public static final int MAX = 1000000;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        boolean check[] = new boolean[MAX];
        int dist[] = new int[MAX];
        check[n] = true; // 수빈이 현재 위치 방문 표시
        dist[n] = 0; // 현재 위치는 걸린 시간 0
        Queue<Integer> q = new LinkedList<Integer>();
        q.add(n);
        while(!q.isEmpty()) {
            int now = q.poll();
            if(now - 1 >= 0) { // 현재 위치에서 -1 했을 때 가능한 경우
                if(check[now - 1] == false) { // 아직 방문하지 않은 경우
                    q.add(now - 1);
                    check[now - 1] = true;
                    dist[now - 1] = dist[now] + 1; // 시간 +1
                }
            }
            if(now + 1 < MAX) { // 현재 위치에서 +1 했을 때 가능한 경우
                if(check[now + 1] == false) { // 아직 방문하지 않은 경우
                    q.add(now + 1);
                    check[now + 1] = true;
                    dist[now + 1] = dist[now] + 1; // 시간 +1
                }
            }
            if(now * 2 < MAX) { // 현재 위치에서 *2 했을 때 가능한 경우
                if(check[now * 2] == false) { // 아직 방문하지 않은 경우
                    q.add(now * 2);
                    check[now * 2] = true;
                    dist[now * 2] = dist[now] + 1; // 시간 +1
                }
            } 
        }
        System.out.println(dist[m]);
    }
}

dist[i] = i를 몇 번만에 방문했는지 여부를 표현한다.
bfs 탐색을 통한 최단거리 구하는 방식으로 풀어주면 되는데 현재 정점에서 -1, +1, *2 가 가능한 경우들을 비교해주는 부분이 필요하다.

결과

백준 13913번 숨바꼭질 4

문제

나의 풀이

import java.util.*;

public class Main {
    public static final int MAX = 1000000;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        boolean check[] = new boolean[MAX];
        int dist[] = new int[MAX];
        int from[] = new int[MAX];
        check[n] = true;
        dist[n] = 0;
        Queue<Integer> q = new LinkedList<Integer>();
        q.add(n);
        while(!q.isEmpty()) {
            int now = q.poll();
            if(now - 1 >= 0) { // 현재 위치에서 -1 했을 때 가능한 경우
                if(check[now - 1] == false) { // 아직 방문하지 않은 경우
                    q.add(now - 1);
                    check[now - 1] = true;
                    dist[now - 1] = dist[now] + 1; // 시간 +1
                    from[now - 1] = now;
                }
            }
            if(now + 1 < MAX) { // 현재 위치에서 +1 했을 때 가능한 경우
                if(check[now + 1] == false) { // 아직 방문하지 않은 경우
                    q.add(now + 1);
                    check[now + 1] = true;
                    dist[now + 1] = dist[now] + 1; // 시간 +1
                    from[now + 1] = now;
                }
            }
            if(now * 2 < MAX) { // 현재 위치에서 *2 했을 때 가능한 경우
                if(check[now * 2] == false) { // 아직 방문하지 않은 경우
                    q.add(now * 2);
                    check[now * 2] = true;
                    dist[now * 2] = dist[now] + 1; // 시간 +1
                    from[now * 2] = now;
                }
            }
        }
        System.out.println(dist[m]);
        
        Stack<Integer> answer = new Stack<>();
        for(int i = m; i != n; i = from[i]) {
            answer.push(i);
        }
        answer.push(n);
        while(!answer.isEmpty()) {
            System.out.print(answer.pop() + " ");
        }
        System.out.println();
    }
}

숨바꼭질 문제와 똑같으나 이동하는 방법도 구해야 한다.
from[i] = 어디에서 왔는지를 나타낸다.
만약 from[next] = now 라면 next는 now에서 왔음을 의미한다.
스택에 from에 있는 정보를 저장시켜서 pop시키면서 이를 출력시키면 이동하는 방법을 구할 수 있다.

결과

백준 14226번 이모티콘

문제

나의 풀이

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int d[][] = new int[n + 1][n + 1];
        for(int i = 0; i <= n; i++) {
            Arrays.fill(d[i], -1);
        }
        Queue<Integer> q = new LinkedList<Integer>();
        q.add(1);
        q.add(0);
        d[1][0] = 0;
        while(!q.isEmpty()) {
            int s = q.poll();
            int c = q.poll();
            if(d[s][s] == -1) { // 아직 복사 안한 경우
                d[s][s] = d[s][c] + 1;
                q.add(s); q.add(s);
            }
            if(s + c <= n && d[s + c][c] == -1) { // 아직 붙여넣기 안한 경우
                d[s + c][c] = d[s][c] + 1;
                q.add(s + c); q.add(c);
            }
            if(s - 1 >= 0 && d[s - 1][c] == -1) { // 아직 삭제 안한 경우
                d[s - 1][c] = d[s][c] + 1;
                q.add(s - 1); q.add(c);
            }
        }
        
        int answer = -1;
        for(int i = 0; i <= n; i++) {
            if(d[n][i] != -1) {
                if(answer == -1 || answer > d[n][i]) {
                    answer = d[n][i];
                }
            }
        }
        System.out.println(answer);
    }
}

클립보드에 몇개가 있는지에 따라서 만들 수 있는 다음 상태가 달라지기 때문에 정점을 나눠줘야 한다.
즉, 화면에 이모티콘의 개수 s와 클립보드에 있는 이모티콘의 개수 c가 중요하다.

• 복사 : (s, c) -> (s, s)
• 붙여넣기 : (s, c) -> (s + c, c)
• 삭제 : (s, c) -> (s - 1, c)
  이렇게 경우의 수를 나누어주고 d배열도 2차원 배열로 만들어서 값을 저장시켜준다.
  클립보드에 있는 이모티콘의 개수를 정확히 모르기 때문에 for문을 0부터 n까지 돌면서 정답을 찾아줘야 한다.

결과