[백준_2503번] 숫자 야구

https://www.acmicpc.net/problem/2503

2503번: 숫자 야구

[문제]

 정보문화진흥원 정보 영재 동아리에서 동아리 활동을 하던 영수와 민혁이는 쉬는 시간을 틈타 숫자야구 게임을 하기로 했다.

• 영수는 1에서 9까지의 서로 다른 숫자 세 개로 구성된 세 자리 수를 마음속으로 생각한다. (예: 324)
• 민혁이는 1에서 9까지의 서로 다른 숫자 세 개로 구성된 세 자리 수를 영수에게 묻는다. (예: 123)
• 민혁이가 말한 세 자리 수에 있는 숫자들 중 하나가 영수의 세 자리 수의 동일한 자리에 위치하면 스트라이크 한 번으로 센다. 숫자가 영수의 세 자리 수에 있긴 하나 다른 자리에 위치하면 볼 한 번으로 센다.

 

예) 영수가 324를 갖고 있으면 

• 429는 1 스트라이크 1 볼이다.
• 241은 0 스트라이크 2 볼이다.
• 924는 2 스트라이크 0 볼이다.
• 영수는 민혁이가 말한 수가 몇 스트라이크 몇 볼인지를 답해준다.
• 민혁이가 영수의 세 자리 수를 정확하게 맞추어 3 스트라이크가 되면 게임이 끝난다. 아니라면 민혁이는 새로운 수를 생각해 다시 영수에게 묻는다.

 

  현재 민혁이와 영수는 게임을 하고 있는 도중에 있다. 민혁이가 영수에게 어떤 수들을 물어보았는지, 그리고 각각의 물음에 영수가 어떤 대답을 했는지가 입력으로 주어진다. 이 입력을 바탕으로 여러분은 영수가 생각하고 있을 가능성이 있는 수가 총 몇 개인지를 알아맞혀야 한다.

 

아래와 같은 경우를 생각해보자.  

• 민혁: 123
• 영수: 1 스트라이크 1 볼.
• 민혁: 356
• 영수: 1 스트라이크 0 볼.
• 민혁: 327
• 영수: 2 스트라이크 0 볼.
• 민혁: 489
• 영수: 0 스트라이크 1 볼.

 

 이때 가능한 답은 324와 328, 이렇게 두 가지이다.

 

 영수는 동아리의 규율을 잘 따르는 착한 아이라 민혁이의 물음에 곧이곧대로 정직하게 답한다. 그러므로 영수의 답들에는 모순이 없다. 민혁이의 물음들과 각각의 물음에 대한 영수의 답이 입력으로 주어질 때 영수가 생각하고 있을 가능성이 있는 답의 총 개수를 출력하는 프로그램을 작성하시오.

 

[입력 조건]

 첫째 줄에는 민혁이가 영수에게 몇 번이나 질문을 했는지를 나타내는 1 이상 100 이하의 자연수 N이 주어진다. 이어지는 N개의 줄에는 각 줄마다 민혁이가 질문한 세 자리 수와 영수가 답한 스트라이크 개수를 나타내는 정수와 볼의 개수를 나타내는 정수, 이렇게 총 세 개의 정수가 빈칸을 사이에 두고 주어진다.

 

[코드]

import java.util.*;

class Game_2503 {
	String num;
	int strike;
	int ball;
	
	public Game_2503(String num, int strike, int ball) {
		this.num=num;
		this.strike=strike;
		this.ball=ball;
	}
}
public class BaekJoon_2503 {
	static ArrayList<Game_2503> arr=new ArrayList<>();
	static boolean[] visited=new boolean[10];
	static int[] num=new int[3];
	static int n,result=0;
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		n=sc.nextInt();
		
		// 민혁이가 물어본 숫자에 대한 영수의 대답을 연결리스트에 저장
		for(int i=0;i<n;i++) 
			arr.add(new Game_2503(sc.next(),sc.nextInt(),sc.nextInt()));
		
		dfs(0);
		System.out.println(result);
	}
	
	static void dfs(int depth) {
		// 3자리의 숫자가 만들어졌다면
		if(depth==3) {
			String n="";
			for(int i=0;i<3;i++)
				n+=num[i];
			
			// 만들어진 숫자가 연결리스트에 저장된 모든 경우와 일치하는지 체크
			for(int i=0;i<arr.size();i++) {
				int s=0,b=0;
				for(int j=0;j<3;j++) {
					// 숫자와 자릿수까지 일치하면 strike
					if(n.charAt(j)==arr.get(i).num.charAt(j))
						s++;
					// 자릿수는 일치하지 않지만 숫자를 포함한다면 ball
					else if(arr.get(i).num.contains(n.charAt(j)+""))
						b++;
				}
				
				// 연결리스트에 저장된 경우와 일치한다면 다음 경우의 수로 넘어간다.
				if(arr.get(i).strike==s&&arr.get(i).ball==b)
					continue;
					// 일치하지 않는다면 해당 수는 패스
					return;
			}
			// 연결리스트의 모든 경우의 수와 일치한다면 가능한 수로 판단하고 count
			result++;
			return;
		}
		
		// 백트래킹을 사용하여 중복되지 않는 3자리 숫자 만들기
		for(int i=1;i<=9;i++) {
			if(!visited[i]) {
				visited[i]=true;
				num[depth]=i;
				dfs(depth+1);
				visited[i]=false;
			}
		}
	}
}

 

[고찰]

 이번 문제는 백트래킹을 사용하여 만들어질 수 있는 모든 숫자를 탐색하는 것이다. 민혁이가 물어본 숫자에 대한 영수의 스트라이크, 볼의 개수를 모두 저장할 수 있는 클래스를 만들고, 입력받은 값을 클래스에 저장해 연결리스트에 삽입한다. 이후 백트래킹을 사용하여 숫자의 중복 없이 만들 수 있는 3자리의 정수를 만들어 연결리스트에 저장된 경우의 수와 모두 일치하는지 확인한다. 이렇게 모든 경우와 일치하는 숫자의 개수가 정답이 된다. 

 해당 문제는 숫자의 중복 없이 3자리의 정수가 만들어지는 경우가 많지 않기 때문에 완전탐색을 사용하여 해결 가능한 문제였다. 또한 클래스를 하나 선언하여 민수가 물어본 숫자에 대한 결과 값을 저장하는 것이 편리했다. 이렇게 필요한 값들을 한번에 저장, 다룰 수 있는 클래스에 좀 더 익숙해져야겠다.