(C++) - 프로그래머스(고득점 kit - (DFS/BFS)) : 타겟 넘버(BFS) 답

programmers.co.kr/learn/courses/30/lessons/43165

코딩테스트 연습 - 타겟 넘버

 

bfs로 구현한 문제였습니다.

 

풀이방법

  1. level이 증가할 수록 +, - 두 가지 경우씩 늘어나기 때문에 q의 size는 두 배씩 증가하게 됩니다. 현재 queue의 size만큼 push를 한다는 것의 의미는 같은 level의 원소들을 의미합니다. 따라서 numbers.size만큼 loop를 돌며 현재 queue size마다 더한값, 뺀 값을 push해주면 됩니다.

  2. push를 마친 후에 q.empty()까지 target과 같은 queue의 원소를 세 준 후 반환하면 됩니다.

 

 

Code

#include <bits/stdc++.h>
using namespace std;

void input(queue <int> &q, int num){
    int x = q.front();
    q.pop();
    for(int i  =0; i < 2; i++)
        !(i % 2) ? q.push(x + num) : q.push(x - num);
}

int bfs(vector <int> &numbers,int target){
    queue <int> q;
    q.push(numbers[0]);
    q.push(-numbers[0]);
    int cnt = 0;
    for(int i = 1; i < numbers.size(); i++){
        int sz = q.size();
        while(sz--) input(q,numbers[i]);
    }

    while(!q.empty()){
        int x = q.front();
        if (x == target) cnt++;
        q.pop();
    }

    return cnt;
}

int solution(vector<int> numbers, int target) {
    return bfs(numbers,target);
}