리모컨문제 푸는데 브루트포스로는 엄두가 안나서 버튼클릭, 이동이 전부 가중치가 1이니깐 BFS로 만들자 하고
public class Num1107 {
public static void main(String[] args) throws IOException {
// TODO Auto-generated method stub
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
int a = Integer.parseInt(bf.readLine());
int b = Integer.parseInt(bf.readLine());
ArrayList ok = new ArrayList();
if(b != 0)
{
String[] str = bf.readLine().split(" ");
for(int i = 0 ; i <= 9 ; i++)
{
int flag = 0;
for(int j = 0 ; j
{
if(Integer.parseInt(str[j]) == i)
{
flag = 1;
break;
}
}
if(flag == 0)
ok.add(i);
}
}
else
{
for(int i = 0 ; i <= 9 ; i++)
ok.add(i);
}
BFS(0, a, ok);
}
public static void BFS(int cur, int result, ArrayList ok)
{
int MAX = 1000000;
int[] check = new int[MAX+1];
Queue q = new LinkedList();
Queue n_q = new LinkedList();
int oklen = ok.size();
for(int i = 0 ; i
{
int n_cur = ok.get(i);
check[n_cur] = 1;
q.add(n_cur);
n_q.add(n_cur);
}
while(!q.isEmpty() && check[result] == 0)
{
cur = q.poll();
if(cur <= (MAX/10)-1)
{
for(int i = 0 ; i
{
int n_cur = cur*10+ok.get(i);
if(check[n_cur] == 0)
{
check[n_cur] = check[cur] + 1;
q.add(n_cur);
n_q.add(n_cur);
}
}
}
}
while(!n_q.isEmpty() && check[result] == 0)
{
cur = n_q.poll();
if(cur+1 <= MAX && check[cur+1] == 0)
{
n_q.add(cur+1);
check[cur+1] = check[cur] + 1;
}
if(cur-1 >= 0 && check[cur-1] == 0)
{
n_q.add(cur-1);
check[cur-1] = check[cur] + 1;
}
}
int result2 = Math.abs(100-result);
if(check[result] == 0 || result2
System.out.println(result2);
else
System.out.println(check[result]);
}
}
진짜 무식하게 각 숫자 누를때 기존숫자*10 +1 부터 기존숫자 *10+9 까지 q.add() 하고
그 후에는 +1, -1할때 q.add() 해서 예외같은것도 다 봉합하고 해서 풀고 개좋아했는데
다음날 백준 인강에서 세워준 전략 듣고 시도하니깐
public class Num1107_2 {
public static void main(String[] args) throws IOException
{
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
int a = Integer.parseInt(bf.readLine());
int b = Integer.parseInt(bf.readLine());
int[] broken = new int????;
if(b != 0)
{
String[] str = bf.readLine().split(" ");
for(int i = 0 ; i
broken[Integer.parseInt(str[i])] = 1;
}
int min = Math.abs(a - 100);
for(int i = 0 ; i <= 1000000 ; i++)
{
String su = Integer.toString(i);
int sulen = su.length();
for(int j = 0 ; j <= sulen; j++)
{
if(j == sulen)
{
min = Math.min(min, Math.abs(i-a)+sulen);
break;
}
if(broken[su.charAt(j) - '0'] == 1)
break;
}
}
System.out.println(min);
}
}
딱 이렇게 컴팩트하게 나오더라
진짜 어떻게 이런 생각을 할 수 있는거지? 짜는데도 얼마 안걸리고
슬프다.. 세상엔 이런 사람들이 넘치고 흐른다는거자나
그냥 웰노운이라 그런데