Algorithm/그래프 탐색

BOJ#14226 이모티콘

밤이2209 2017. 4. 3. 15:57

BOJ#14226 이모티콘


* 문제

* 풀이

푸는데 고생했지만 재밌는 문제입니다.
처음에는 1000개의 테스트케이스 중 11개만 틀렸는데, 원인을 찾기 쉽지 않았습니다.

BFS 돌리면서 visited 배열로 정점을 중복 방문하지 않게 구현했는데, 이것이 실패 원인이었습니다.

왜냐하면 정점의 값이 같더라도 클립보드에 어떤 내용이 들어있는지에 따라 향후 탐색할 수 있는 정점이 달라지기 때문입니다.

따라서 visited 배열을 discovered 배열의 개념으로 바꾸고
discovered 배열을 

(기존)
boolean[][] discovered = new boolean[정점]

(변경)
boolean[][] discovered = new boolean[정점][클립보드]

으로 선언하였습니다.


(참고) 테스트케이스와 답 <-- 누르기

* 나의 코드


https://github.com/stack07142/BOJ/blob/master/BOJ%2314226_Emoticon/src/Main.java


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

/**
 * BOJ#14226 이모티콘
 * https://www.acmicpc.net/problem/14226
 */

public class Main {

    static boolean[][] discovered = new boolean[10000][10000];

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

        // input
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int S = Integer.parseInt(br.readLine());

        // solve - bfs
        PriorityQueue<Node> queue = new PriorityQueue<Node>();

        queue.add(new Node(1, 0, 0));

        while (!queue.isEmpty()) {

            Node u = queue.poll();

            if (u.value == S) {

                System.out.println(u.cost);
                break;
            }

            // copy
            if(!discovered[u.value][u.value]) {

                queue.add(new Node(u.value, u.value, u.cost + 1));
                discovered[u.value][u.value] = true;
            }

            // paste
            int addedValue = u.value + u.clipboard;
            if (!discovered[addedValue][u.clipboard] && addedValue < 10000) {

                queue.add(new Node(addedValue, u.clipboard, u.cost + 1));
                discovered[addedValue][u.clipboard] = true;
            }

            // delete
            int deletedValue = u.value - 1;
            if (deletedValue >= 0 && !discovered[deletedValue][u.clipboard]) {

                queue.add(new Node(deletedValue, u.clipboard, u.cost + 1));
                discovered[addedValue][u.clipboard] = true;
            }
        }
    }
}

class Node implements Comparable<Node> {

    int value;
    int clipboard;
    int cost;

    Node(int value, int clipboard, int cost) {

        this.value = value;
        this.clipboard = clipboard;
        this.cost = cost;
    }

    @Override
    public int compareTo(Node o) {

        return this.cost < o.cost ? -1 : 1;
    }
}





저작자표시 비영리 동일조건

'Algorithm > 그래프 탐색' 카테고리의 다른 글

BOJ#1987 알파벳 (Letters)  (0) 2017.04.06
BOJ#9376 탈옥  (1) 2017.04.04
BOJ#5014 스타트링크  (0) 2017.04.02
BOJ#2468 안전 영역  (0) 2017.04.02
BOJ#2206 벽 부수고 이동하기  (0) 2017.04.02

'Algorithm/그래프 탐색'의 다른글

  • 현재글BOJ#14226 이모티콘

관련글

티스토리툴바