📒활용 개념

DFS와 BFS를 이용한 풀이
그 중 DFS를 선택하여 활용하였다.

DFS와 BFS에 대한 개념

📌문제설명

어피치와 라이언의 양궁대회에서 어피치가 화살 n개를 먼저 쏘고 라이언이 n개를 쏜다.

• 점수계산
  • 과녁의 점수는 0~10점
  • 만약 같은 점수 칸에 어피치가 a발 라이언이 b발이라면
    • a>=b 인 경우 어피치의 점수
    • a< b 인 경우 라이언의 점수
    • 둘다 0점인 경우 점수 없음
      어피치가 10발을 모두 쏜 상태에서 라이언이 가장 큰 점수차로 이기는 경우를 구하시오.
      (단 같은 점수 차이라면 낮은 점수를 많이 쏜 경우리 구하시오.)

📌구현

#include <string>
#include <vector>
#include <iostream>

using namespace std;

int maxScore=-100;									//가장 큰 점수차이
vector<int> answer(11, -1);							//작은 점수를 가장 많이 쏜 경우

//점수 계산 함수
int makeScore(vector<int> RU, vector<int> AU){		
    int rs=0;										//라이언 점수
    int as=0;										//어피치 점수
    for(int i=10; i>=0; i--){
        if(RU[i]>AU[i]){							//a<b인 경우
            rs=rs+(10-i);
        }
        else if (AU[i]>0){							//a>=b인 경우
            as=as+(10-i);
        }
    }
    return (rs-as);									//점수 차이 계산
}

//DFS 활용한 함수
void dfs(int target, int useable, vector<int>& ryan, vector<int> appeach)
//현제 과녁 점수, 사용 가능 화살 수, 라이언의 점수당 화살 갯수, 어피치의 점수당 화살 갯수
{
    if(target==10 || useable==0){					//마지막 과녁 또는 화살
        ryan[10]+=useable;							//남은 화살은 모두 0점
        
        if(makeScore(ryan, appeach)>0&&makeScore(ryan, appeach)>maxScore){
            maxScore=makeScore(ryan, appeach);		//가장 큰 점수차이 보다 큰 경우
            answer=ryan;
        }
        else if(makeScore(ryan, appeach)>0&&makeScore(ryan, appeach)==maxScore)		   {											//가장 큰 점수 차이와 같은 경우
            for(int i=10; i>=0; i--){
                if(ryan[i]>answer[i]){				//작은 점수를 많이 쏜 경우 비교
                    answer=ryan;
                    break;
                }
                else if (ryan[i]<answer[i]){
                    break;
                }
            }
        }
        ryan[10]-=useable;							//0점의 화살 갯수 초기화
        return ;
    }
    
    else{
        dfs(target+1, useable, ryan, appeach);      //점수를 얻지 않음.
        if(appeach[target]+1 <= useable){
            ryan[target]=appeach[target]+1;			//사용 화살 갯수 적용
            dfs(target+1, useable-(appeach[target]+1), ryan, appeach); //점수를 얻음
            ryan[target]=0;							//사용 하살 갯수 초기화
        }
    }
}

vector<int> solution(int n, vector<int> info) {
    vector<int> ryanUse(11, 0);						// 라이언 화살 사용 갯수
    dfs(0, n, ryanUse, info);
    
    if(answer[0]==-1){								//라이언이 이길 수 없는 경우
        vector<int> a(1,-1);
        return a;
    }
    
    return answer;
}

📌주의점

• DFS를 활용한 함수 제작
• 점수 계산의 경우의 수
  - 서로 0점인 경우의 점수 계산
• DFS함수의 Parameter가 어떤 것이 필요한지 생각.