글 읽기 - 100% 다되서 자꾸 틀리는데 뭐가 문제인지 모르겠네요...

ciwnyg0815 5년 전 0

BFS로 풀었습니다.

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <queue>
#include <algorithm>


using namespace std;

int checkAvailable(int n);
int digits(int n);
int bfs(int ch, int n);

// 0이면 정상, 1이면 고장
int buttons[10] = {0, };
int visit[1000000] = {0, };

int main(){
    
    int ch=100, n, errorNum, temp;

    cin >> n;
    cin >> errorNum;

    // 고장난 버튼 저장.
    for(int i=0; i<errorNum-1; i++){
        scanf("%d ", &temp);
        buttons[temp] = 1;
    }
    if(errorNum > 0){
        scanf("%d", &temp);
        buttons[temp] = 1;
    }
    

    cout << bfs(ch, n) << '\n'; 

    return 0;
}

int bfs(int ch, int n){
    
    queue<int> q;
    int temp, time = 0;

    q.push(n);

    while(true){
        int size = q.size();
        for(int i=0; i<size; i++){
            temp = q.front();
            q.pop();

            // 100 기준으로 버튼 누르는 거보다 그냥 +-로 하는게 나으면, 그렇게 반환
            if(digits(temp) > abs(temp-ch)){
                return time + abs(temp-ch);
            }
            if(checkAvailable(temp)){
                return time + digits(temp);
            }

            if(temp-1 >= 0 && visit[temp-1] == 0){
                visit[temp-1] = 1;
                q.push(temp-1);
            }
            if(temp+1 <= 999999 && visit[temp+1] == 0){
                visit[temp+1] = 1;
                q.push(temp+1);
            } 
        }
        time++;
    }

    return 1;
}


// 불량버튼 안 누르고 호출 가능한지 확인.
int checkAvailable(int n){
    vector<int> nums;

    if(n==0) nums.push_back(0);
    while(n>0){
        nums.push_back(n%10);
        n /= 10;
    }

    for(int i=0; i<nums.size(); i++){
        if(buttons[nums[i]] == 1) return 0;
    }
    return 1;
}

// 자릿수 계산하여 반환
int digits(int n){

    int ret = 0;

    if(n==0) return 1;

    while(n>0){
        n /= 10;
        ret++;
    }

    return ret;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

100% 다되서 자꾸 틀리는데 뭐가 문제인지 모르겠네요...

ciwnyg0815 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말