백준 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까지 돌면서 정답을 찾아줘야 한다.

결과

profile
가보자고

0개의 댓글

Powered by GraphCDN, the GraphQL CDN