[백준] 2503 숫자 야구 - 완전탐색(DFS) + 아이디어 JAVA

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

2503번: 숫자 야구

문제풀이

DFS를 활용하여 모든 숫자 조합을 구한뒤, 조건에 맞는 것들만 선택하여 result += 1 해주는 문제였습니다.

여기서 모든 숫자 조합은

123 ~ 987 까지 입니다. (0 은 존재하지 않고, 각 숫자들은 한가지로만 이루어져있기에 999가 아닌 987 입니다. )

 

모든 숫자조합을 돌면서, 질문한 숫자와 비교하여 

4
123 1 1
356 1 0
327 2 0
489 0 1

여기서 

만약 기준숫자가 "567" 이라고 가정합니다.

123 부터 다 돌아서 567 숫자가 되었을때,

567은 123, 356, 327, 489 와 비교하게 됩니다.

567과 123을 비교해보면 Strike와 Ball 모두 증가하지 않습니다. 그러므로 StrikeCount = 0, BallCount = 0 입니다.

이미 StrikeCount =0 이고, BallCount = 0 이기에 질문했을때의 답인 AnswerStrike = 1, AnswerBall = 1 과 다르기에 이미 반복문은 종료됩니다. 

사실상 이미 더 검사를 해도 의미가 없습니다만, 예시를 위해 더 진행해보겠습니다.

567과 356을 비교해보면 StrikeCount = 0, BallCount = 2 입니다. AnswerStrike = 1, AnswerBall = 0 이기에 이것또한 다릅니다.

 

위의 검사들을 계속해서 진행하면 맞는 조건들이 있습니다.

해당 숫자들을 답으로 간주하고 result += 1 을 하면 답이 나옵니다.

 

 

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {	
	public static int N, M;
	public static Node[] num;
	public static int result = 0;
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	N = Integer.parseInt(st.nextToken()); // 민혁이가 영수에게 질문한 횟수
    	num = new Node[N];
    	
    	for(int i=0;i<N;i++) {
    		st = new StringTokenizer(br.readLine());
    		int a = Integer.parseInt(st.nextToken());
    		int b = Integer.parseInt(st.nextToken());
    		int c = Integer.parseInt(st.nextToken());
    		num[i] = new Node(a, b, c);
    	}
    	
    	
    	//123 부터 987 까지 가능하므로 반복문 설정합니다.
    	for(int i=123; i<=987; i++) {
    		int firstNum = i / 100;
    		int secondNum = ( i / 10 ) % 10;
    		int thirdNum = ( i % 10);
    		
    		
    		//1에서 9까지의 숫자만 가능합니다.
    		if(firstNum == 0 || secondNum == 0 || thirdNum == 0) continue;
    		
    		//모든 숫자의 수가 달라야합니다.
    		if( firstNum == secondNum || firstNum == thirdNum || secondNum == thirdNum ) continue;
    		
    		boolean Sameflag = true;
    		
    		for(int j=0;j<N;j++) {
    			int strikeCount = 0;
    			int ballCount = 0;
    			
    			Node node = num[j];
    			int QuestionNum = node.num;
	    		int QuestionFirstNum = QuestionNum / 100; //첫번째 자리
	    		int QuestionSecondNum = ( QuestionNum / 10 ) % 10; //두번쨰 자리
	    		int QuestionThirdNum = QuestionNum % 10; //세번쨰자리
    			int AnswerStrike = node.strike; //질문한 숫자의 Strike 개수
    			int AnswerBall = node.ball; //질문한 숫자의 Ball 개수
    			
    			if( firstNum == QuestionFirstNum ) strikeCount += 1;
    			if( secondNum == QuestionSecondNum ) strikeCount += 1;
    			if( thirdNum == QuestionThirdNum ) strikeCount += 1;
    			
    			if( firstNum == QuestionSecondNum || firstNum == QuestionThirdNum) ballCount += 1;
    			if( secondNum == QuestionFirstNum || secondNum == QuestionThirdNum) ballCount += 1;
    			if( thirdNum == QuestionFirstNum || thirdNum == QuestionSecondNum) ballCount += 1;
    			
    			
    			//하나라도 Strike와 Ball이 일치하지 않는다면 해당 숫자는 조건에 맞지 않습니다.
    			if( strikeCount != AnswerStrike || ballCount != AnswerBall) {
    				Sameflag = false;
    				break;
    			}
    			
    		}
    		
    		if(Sameflag == true) {
    			result += 1;
    		}
    		
    	}
    	
    	System.out.println(result);
	}
}

class Node{
	int num;
	int strike;
	int ball;
	public Node(int num, int strike, int ball) {
		this.num = num;
		this.strike = strike;
		this.ball = ball;
	}
}