[백준] 14226 이모티콘(Gold.4) - BFS

문제

이모티콘

코드

시도 1 - O

큐에 {현재 값, 시간, 현재 복사중인 값} 값을 넣고 아래 조건에 따라 새로운 노드를 생성하여 큐에 삽입하는 방식으로 구현했다.

1. 현재 값 < 목표 값(S) -> 복사&붙여넣기와 붙여넣기
2. 현재 값 > 목표 값(S) -> 삭제
3. 현재 값 == 목표 값(S) -> 지금까지 나온 최소 시간과 비교하여 작은 값을 min 변수에 삽입(min = Math.min(min, cur[1]))
   
   예시를 입력하면 정답이 출력되지만 막상 제출하면 틀렸다고 나온다. 로직이 잘못된 것 같아서 새로운 로직으로 풀어봤다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

public class _14226 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int S = Integer.parseInt(br.readLine());
        System.out.println(bfs(1, S));
    }

    public static int bfs(int start, int S) {
        // {현재 값, 시간, 현재 복사중인 값}
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[] {start, 0, 0});

        int min = Integer.MAX_VALUE;
        while (!q.isEmpty()) {
            int[] cur = q.poll();
            // 현재 값 == 목표 값 -> return 시간
            if (cur[0] == S) {
                min = Math.min(min, cur[1]);
            }
            // 현재 값 < 목표 값 -> 붙여넣기 & 복사-붙여넣기
            else if (cur[0] < S) {
                if (cur[1] == 0) {
                    q.add(new int[]{cur[0] + cur[0], cur[1] + 2, cur[0]});
                    continue;
                }
                // 붙여넣기
                q.add(new int[]{cur[0] + cur[2], cur[1] + 1, cur[2]});
                // 복사 + 붙여넣기
                q.add(new int[]{cur[0] + cur[0], cur[1] + 2, cur[0]});
            }
            // 현재 값 > 목표 값 -> 취소만 가능
            else {
                q.add(new int[]{cur[0] - 1, cur[1] + 1, cur[2]});
            }
        }
        return min;
    }
}

시도 2 - X

이 코드도 정답이 출력되지만 메모리 초과가 뜬다..
메모리 초과는 방문 여부 체크(중복 상태 처리)를 안해서 생긴 문제였다. 그리고 애초에 삭제 연산도 안 해서 잘못된 코드다. 방문 여부 체크와 삭제 연산까지 추가하여 새로운 코드를 작성했다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

public class _14226 {
    static class Emoji {
        int value, copy, time;
        Emoji(int value, int copy, int time) {
            this.value = value;
            this.copy = copy;
            this.time = time;
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int S = Integer.parseInt(br.readLine());
        System.out.println(bfs(S));
    }

    public static int bfs(int S) {
        // {현재 값, 현재 복사 중인 값, 시간}
        Queue<Emoji> q = new LinkedList<>();
        q.add(new Emoji(1, 0, 0));

        int min = Integer.MAX_VALUE;
        while (!q.isEmpty()) {
            Emoji e = q.poll();

            // 최초 구한 값이 최솟값이므로 바로 반환
            if (e.value == S) {
                return e.time;
            }

            if (e.value != e.copy) {
                // 복사
                q.add(new Emoji(e.value, e.value, e.time + 1));
                // 붙여넣기
                q.add(new Emoji(e.value + e.copy, e.copy, e.time + 1));
            } else {
                // 붙여넣기
                q.add(new Emoji(e.value + e.copy, e.copy, e.time + 1));
            }
        }
        return -1;
    }
}

시도 3 - O

방문 여부를 체크하는 배열을 {현재 값, 복사 값} 형태로 선언하고 방문 하지 않은 값은 복사, 붙여넣기, 삭제 연산 모두 실행하도록 변경했다. 그리고 연산을 처리하다 목표 값(S)가 나오면 바로 반환하도록 작성했다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

public class _14226 {
    static class Emoji {
        int value, copy, time;
        Emoji(int value, int copy, int time) {
            this.value = value;
            this.copy = copy;
            this.time = time;
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int S = Integer.parseInt(br.readLine());
        System.out.println(bfs(S));
    }

    public static int bfs(int S) {
        // {현재 값, 현재 복사 중인 값, 시간}
        Queue<Emoji> q = new LinkedList<>();
        q.add(new Emoji(1, 0, 0));

        boolean[][] visited = new boolean[1001][1001];
        visited[1][0] = true;

        int min = Integer.MAX_VALUE;
        while (!q.isEmpty()) {
            Emoji e = q.poll();

            // 최초 구한 값이 최솟값이므로 바로 반환
            if (e.value == S) {
                return e.time;
            }

            // 복사
            if (!visited[e.value][e.value]) {
                q.add(new Emoji(e.value, e.value, e.time + 1));
                visited[e.value][e.value] = true;
            }
            // 붙여넣기
            if (e.value+e.copy <= S && !visited[e.value+e.copy][e.copy]) {
                q.add(new Emoji(e.value + e.copy, e.copy, e.time + 1));
                visited[e.value + e.copy][e.copy] = true;
            }
            // 삭제
            if (e.value - 1 >= 0 && !visited[e.value - 1][e.copy]) {
                q.add(new Emoji(e.value - 1, e.copy, e.time + 1));
                visited[e.value - 1][e.copy] = true;
            }
        }
        return -1;
    }
}

결론

풀 때는 너무 어려웠는데 막상 풀고 보니 다른 BFS 문제와 마찬가지로 방문 여부를 체크하여 세 가지 연산(복사, 붙여넣기, 삭제)를 실행하면 되는 간단한 문제였다. 왜 이렇게 복잡하게 생각한거지... 잠을 못자서 그런가 .. 반성하자