백준 12869번 뮤탈리스크 C++

백준 12869번 뮤탈리스크 문제 풀이 입니다

이 문제 같은 경우 BFS를 활용해 해결해주었습니다.

우선 각 SCV의 피가 몇인지 받아옵니다

cin >> n;
	
for (int i = 0; i < n; i++){
	cin >> arr[i];
}

이후 문제에 나온 3가지를 케이스를 이용해
총 6개의 경우의 수를 만들어줍니다

 int atk[6][3] = { // 경우의 수는 6가지 있다 3 x 2 (조합) 
 	{9, 3, 1},
 	{9, 1, 3},
 	{3, 1, 9},
 	{3, 9, 1},
 	{1, 3, 9},
 	{1, 9, 3}
 };

다른 BFS 문제와 달리 pair를 사용하지 못하기에
struct를 통해 세 가지 데이터(1번 scv, 2번 scv, 3번 scv)를 넣을 수 있는 자료형을 만들어줍니다

 struct SCV { // tuple 대신 struct 사용 
 	int a, b, c;
 };

이후 BFS를 구현해줍니다.

queue 만든 후 각 scv의 체력을 넣고 모든 scv의 체력이 0이 될 때까지 순회합니다

각 코드의 기능

while(q.size())

queue의 사이즈가 0(false)이 될때까지 순회

if(visited[0][0][0]) break; 

모든 scv의 체력이 0이 되면 break하고 탈출

• 여기서 가장 처음 체력이 0이 되는 경우
• = SCV를 파괴하기 위한 공격 횟수의 최솟값
  
  

int na = max(0, a - atk[i][0]);
int nb = max(0, b - atk[i][1]); 
int nc = max(0, c - atk[i][2]); 

max를 통해 음수가 되는걸 방지한다

• 덕분에 위 코드에서 break가 가능함
  
  

 visited[na][nb][nc] = visited[a][b][c] + 1;  
 q.push({na, nb, nc}); 

break 직전에 na, nb, nc의 값은 0이 됨

전체 코드

 int bfs(int a, int b, int c) {
 	queue<SCV> q;
 	visited[a][b][c] = 1; // 나중에 빼주어야 하는 값이다 
 	q.push({a, b, c});
 	
 	while(q.size()) {
 	    int a = q.front().a; 
        int b = q.front().b; 
        int c = q.front().c; 
        q.pop();
        if(visited[0][0][0]) break; 
        for(int i = 0; i < 6; i++){
            int na = max(0, a - atk[i][0]);
            int nb = max(0, b - atk[i][1]); 
            int nc = max(0, c - atk[i][2]); 
            if(visited[na][nb][nc]) continue;
            visited[na][nb][nc] = visited[a][b][c] + 1;  
            q.push({na, nb, nc}); 
        }
	}
	
	return visited[0][0][0] - 1;
 }

알게된 점

• tuple 대신 struct를 사용하면 더 편리하게 사용이 가능하다
• max를 통해 음수값을 방지해줄 수 있다
  
  
  
  

감사합니다.