백준 2503 숫자야구 파이썬 문제풀이 (python 완전탐색, 재귀, 백트래킹)

문제 보러가기

 

백준 숫자야구 파이썬 문제풀이 

숫자야구는 저번에 풀었었지만, 이번에는 재귀를 사용해서 풀어볼 것이다. 

 

재귀로 각각의 중복되지 않은 세 자리 자연수를 검사하고, 

그 안에서 모든 조건을 만족하는 수의 개수를 카운트 하는 방식으로 진행하면 될 것이다.

 

정답 코드 1

n = int(input())
answer = 0

def check(number, question, strk, ball):
    s = 0
    b = 0
    for i in range(3):
        if number[i] == int(question[i]):
            s+=1
        elif int(question[i]) in number:
            b+=1
    if strk == s and ball == b:
        return True
    else:
        return False

def recur(lst, depth):
    global answer
    if depth == 3:
        cnt = 0
        for i in range(n):
            if check(lst, str(num[i]), strike[i], ball[i]):
                cnt+=1
        if cnt == n:
            answer+=1
        return
    for i in range(1,10):
        if i not in lst:
            recur(lst+[i], depth+1)

num = [0 for _ in range(n)]
strike = [0 for _ in range(n)]
ball = [0 for _ in range(n)]
for i in range(n):
    num[i], strike[i], ball[i] = map(int,input().split())
recur([],0)
print(answer)

recur 재귀함수를 이용해서 중복 없는 숫자 세 자리를 각각 접근하고

check로 모두 만족하면 답 카운트를 센다.

 

여기서 asnwer는 global 변수임을 재귀함수 안에서 알려주어야한다.

이번에는 숫자 야구를 재귀함수로 풀어보았다~

정답 코드 2

사실 이렇게 재귀를 반복문 처럼 쓰지 않고, 

이번에는 질문을 기준으로 재귀함수를 사용해보자.

 

import sys

n = int(input())
answer = 0

sys.setrecursionlimit(99999)

def check(number, question, strk, ball):
    s = 0
    b = 0
    for i in range(3):
        if number[i] == question[i]:
            s+=1
        elif question[i] in number:
            b+=1
    if strk == s and ball == b:
        return True
    else:
        return False

def is_valid(num):
    # 각 자리 숫자가 서로 다르고 0이 포함되지 않는지 확인
    num_str = str(num)
    return len(set(num_str)) == 3 and '0' not in num_str

def recur(checkCnt, number):
    global answer
    if checkCnt == n:
        answer+=1
        recur(0, number + 1)
        return
    if number == 1000:
        return
    if not is_valid(number):
        recur(0, number + 1)
        return
    if check(str(number), str(num[checkCnt]), strike[checkCnt], ball[checkCnt]):
        recur(checkCnt+1,number)
    else:
        recur(0, number+1)

num = [0 for _ in range(n)]
strike = [0 for _ in range(n)]
ball = [0 for _ in range(n)]
for i in range(n):
    num[i], strike[i], ball[i] = map(int,input().split())
recur(0,100)
print(answer)

checkCnt를 이용해서 질문을 기준으로 재귀를 돌면

범위나 숫자 중복, 0이 들어가지 않는 조건 등 여러 조건을 잘 맞추어주어야한다.

 

조건 만족 개수를 재귀의 depth로 잡아서

조건을 n개 모두 만족하는 경우에 answer를 증가한다. 

 

이렇게 다른 방법들로 숫자 야구를 해결해보았다`!