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 |