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