풀이 방법
BFS 방법으로 풀이했다.
게시판에 있던 테스트케이스는 모두 맞았는데 95퍼정도에서 틀렸다고 나와서 헤맸다.
방문한 채널을 확인하는 과정이 문제였다.
처음부터 방문했다고 체크하게 되면 101이 방문됐다고 확인되서 1011, 1012 같이 101 다음에 채널을 클릭하지 못해서 틀렸다고 풀이됐다.
그래서 3번째 부터 방문됐다고 확인해서 모두 가능하도록 했다.
내 코드
package com.company;
import java.io.*;
import java.util.*;
public class Main {
static int N, M;
static int start = 100;
static boolean[] visited;
static ArrayList<Integer> list = new ArrayList<>();
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
N = Integer.parseInt(br.readLine());
M = Integer.parseInt(br.readLine());
visited = new boolean[1000001];
for (int i = 0; i < 10; i++) {
list.add(i);
}
if (M != 0) {
st = new StringTokenizer(br.readLine());
for (int i = 0; i < M; i++) {
list.remove((Integer) Integer.parseInt(st.nextToken()));
}
}
PriorityQueue<Node> pq = new PriorityQueue<>();
pq.add(new Node(false, start, 0));
while (!pq.isEmpty()) {
Node node = pq.poll();
if (node.num > 1000000 || visited[node.num]) {
continue;
}
if (node.count > 3)
visited[node.num] = true;
if (node.num == N) {
System.out.println(node.count);
break;
}
if (node.num < N)
pq.add(new Node(true, node.num + 1, node.count + 1));
if (node.num > N)
pq.add(new Node(true, Math.max(node.num - 1, 0), node.count + 1));
if (!node.click)
for (int i = 0; i < list.size(); i++) {
if (node.count == 0) {
pq.add(new Node(false, list.get(i), node.count + 1));
} else {
pq.add(new Node(false, (node.num * 10) + list.get(i), node.count + 1));
}
}
}
}
}
class Node implements Comparable<Node> {
boolean click;
int num;
int count;
public Node(boolean click, int num, int count) {
this.click = click;
this.num = num;
this.count = count;
}
@Override
public int compareTo(Node o) {
return this.count - o.count;
}
}
'코딩테스트 > [백준] 코딩테스트 연습' 카테고리의 다른 글
램프 - 1034번 (0) | 2021.11.26 |
---|---|
감소하는 수 - 1038번 (0) | 2021.11.25 |
미친 로봇 - 1405번 (0) | 2021.11.22 |
음식 평론가 - 1188번 (0) | 2021.11.22 |
공약수 - 2436번 (0) | 2021.11.16 |