[DFS/BFS/완전탐색] 2503번 - 숫자 야구(DFS, 완전탐색)

[백준] 2503번 - 숫자 야구

굉장히 익숙한 소재라 문제를 이해하고 설계를 하는데 어려움이 없었으나 오류를 고치느라 시간이 좀 걸렸다. 서로 다른 숫자로 구성된 세자리수를 영수가 생각하고 있을 때, (민혁이가 질문한 세자리수, 스트라이크 개수, 볼 개수)를 보고 가능성이 있는 답의 총 개수를 구하는 문제로 전형적인 완전탐색 문제다. 영수가 생각할 수 있는 수의 모든 경우의 수는 순서가 상관이 있기 때문에 순열로 풀 수 있는데 DFS를 이용하거나 permutations를 이용한 방식 2가지가 있다.

(풀이1) DFS 이용

풀이 시간: 40분 이내

1) 문제 해결 아이디어

<동작 과정>

1. 깊이가 3일 때 종료

num이 세자리수가 되었으므로 종료

1-1. 각 질문(세자리수)에 대해 스트라이크, 볼 개수에 모순이 생기는지 검사

1-1-1. 현재수(num)과 질문 세자리수(target) 값의 각 자리숫자를 비교하여 스트라이크, 볼, 개수 세기

1-1-2. 위에서 센 스트라이크, 볼 개수가 질문 세자리수 결과값과 다르다면 종료

1-2. 각 세자리수에 대한 스트라이크, 볼 개수에 모순이 없다면 가능성있는 정답 개수(answer) 1 증가

2. 9개 숫자 중 이전에 선택한 수가 아닌 수 한개 선택하기

2-1. 이전에 선택한 수가 아니라면 dfs 호출

 

첫번째 오류. 틀렸습니다

13줄~ 에 각 자리수를 검사해 스트라이크, 볼 개수를 세는 부분에서 오류가 있었다.

num[j]를 num[i]라고 잘못 설정하는 바람에 제대로된 값이 나오지 않았다.

 

2) 소스코드

n = int(input())  # 질문 횟수
# 세자리수, 스트라이크 개수, 볼 개수
graph = [list(map(int, input().split())) for _ in range(n)]
num = []    # 암호
answer = 0  # 가능성이 있는 답 개수

# DFS
def dfs(depth):
  if depth == 3:
    global answer
    # 모든 질문에 대해 검사
    for i in range(n):
      # 각 자리수 검사(스트라이크, 볼 개수 세기)
      strike, ball = 0, 0
      for j in range(3):
        target = str(graph[i][0])
        # j번째 자리수가 같다면 스트라이크
        if int(target[j]) == num[j]:  strike += 1
        # 자리수는 다르지만 있다면 볼
        elif int(target[j]) in num:  ball += 1
      # 스트라이크, 볼 수가 하나라도 다르다면 종료
      if strike != graph[i][1] or ball != graph[i][2]:
        return  
    #print(num)
    answer += 1  # 모든 질문에 통과하면 정답 개수 변경
    return     
  # 9개 숫자중에 하나 선택하기
  for i in range(1, 10):
    # 선택하지 않은 수라면
    if i not in num:    
      num.append(i)
      dfs(depth + 1)
      num.pop()

dfs(0)
print(answer)

(풀이2) permutations 이용

풀이 시간: 20분 이내

1) 문제 해결 아이디어

기본적인 아이디어는 똑같고 다만 permutations를 이용하여 순열을 구할 뿐이다.

 

2) 소스코드

from itertools import permutations

n = int(input())  # 질문 횟수
# 세자리수, 스트라이크 개수, 볼 개수
graph = [list(map(int, input().split())) for _ in range(n)]
numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9]  # 가능한 숫자
answer = 0  # 가능성이 있는 답 개수

# (1~9)에서 3개 뽑기
for num in permutations(numbers, 3):
  isAnswer = True  # 정답 여부
  # 모든 질문에 대해 검사
  for i in range(n):
    if not isAnswer:  break
    # 각 자리수 검사(스트라이크, 볼 개수 세기)
    strike, ball = 0, 0
    for j in range(3):
      target = str(graph[i][0])
      # j번째 자리수가 같다면 스트라이크
      if int(target[j]) == num[j]:  strike += 1
      # 자리수는 다르지만 있다면 볼
      elif int(target[j]) in num:  ball += 1
    # 스트라이크, 볼 수가 하나라도 다르다면 종료
    if strike != graph[i][1] or ball != graph[i][2]:
      isAnswer = False
      break 
  if isAnswer:  answer += 1  # 모든 질문에 통과하면 정답 개수 변경
print(answer)