[백준 3주차 - 12869] 뮤탈리스크 (Java)

📌문제

 

 

📝 풀이과정

처음에는 내림차순 정렬을 해서 9,3,1 차례로 빼면서 모두 0이하일 때까지 반복하면 최솟값을 구할 수 있다고 생각했다... 하지만 예외1에서도 그 방법은 맞지 않았다  너무 단순하게 생각한 것이다😓

 

단순하게 9,3,1 만 빼는 것이 아니라 6가지의 경우의 수가 있다

 

 

이렇게 그래프로 나타내보면 모든 경우의 수에서 (0,0,0)에 도달하는 최소의 횟수를 구할 수 있다. 즉, 레벨별로 탐색하여 최단거리를 구하는 개념으로 생각해보면 BFS로 풀 수 있는 것을 알 수 있다.

 

 

💻코드

import java.util.Scanner;
import java.io.*;
import java.util.*;

public class Main{
	static int n;
	static int scv[]=new int[3];
	static int visited[][][]=new int[64][64][64];
	static Queue<Pair> queue=new LinkedList<>();
	static int [][] dn={
		{9,3,1},
		{9,1,3},
		{3,1,9},
		{3,9,1},
		{1,3,9},
		{1,9,3}
	};
	static class Pair{
		int a,b,c;
		Pair(int a,int b,int c){
			this.a=a;
			this.b=b;
			this.c=c;
		}
	}
	static int solve(int a,int b,int c){
		visited[a][b][c]=1;
		queue.add(new Pair(a,b,c));
		
		while(!queue.isEmpty()){
			Pair front=queue.poll();
			if(visited[0][0][0]!=0) break;
			for(int i=0;i<6;i++){
				int na=Math.max(0,front.a-dn[i][0]);
				int nb=Math.max(0,front.b-dn[i][1]);
				int nc=Math.max(0,front.c-dn[i][2]);
				
				if(visited[na][nb][nc]!=0) continue;
				visited[na][nb][nc]=visited[front.a][front.b][front.c]+1;
				queue.add(new Pair(na,nb,nc));
			}
		}
		return visited[0][0][0]-1;
	} 
    public static void main(String[] args) throws IOException{
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		
		n=Integer.parseInt(br.readLine());
		String[] input=br.readLine().split(" ");
		for(int i=0;i<n;i++){
			scv[i]=Integer.parseInt(input[i]);
		}
		System.out.println(solve(scv[0],scv[1],scv[2]));
	}
}