[백준 1057번: 토너먼트] 파이썬 풀이 _ 브루트포스 알고리즘

 

1057번: 토너먼트

---

문제

김지민은 N명이 참가하는 스타 토너먼트에 진출했다. 토너먼트는 다음과 같이 진행된다. 일단 N명의 참가자는 번호가 1번부터 N번까지 배정받는다. 그러고 난 후에 서로 인접한 번호끼리 스타를 한다. 이긴 사람은 다음 라운드에 진출하고, 진 사람은 그 라운드에서 떨어진다. 만약 그 라운드의 참가자가 홀수명이라면, 마지막 번호를 가진 참가자는 다음 라운드로 자동 진출한다. 다음 라운드에선 다시 참가자의 번호를 1번부터 매긴다. 이때, 번호를 매기는 순서는 처음 번호의 순서를 유지하면서 1번부터 매긴다. 이 말은 1번과 2번이 스타를 해서 1번이 진출하고, 3번과 4번이 스타를 해서 4번이 진출했다면, 4번은 다음 라운드에서 번호 2번을 배정받는다. 번호를 다시 배정받은 후에 한 명만 남을 때까지 라운드를 계속 한다.

마침 이 스타 대회에 임한수도 참가했다. 김지민은 갑자기 스타 대회에서 우승하는 욕심은 없어지고, 몇 라운드에서 임한수와 대결하는지 궁금해졌다. 일단 김지민과 임한수는 서로 대결하기 전까지 항상 이긴다고 가정한다. 1 라운드에서 김지민의 번호와 임한수의 번호가 주어질 때, 과연 김지민과 임한수가 몇 라운드에서 대결하는지 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 참가자의 수 N과 1 라운드에서 김지민의 번호와 임한수의 번호가 순서대로 주어진다. N은 2보다 크거나 같고, 100,000보다 작거나 같은 자연수이고, 김지민의 번호와 임한수의 번호는 N보다 작거나 같은 자연수이고, 서로 다르다.

출력

첫째 줄에 김지민과 임한수가 대결하는 라운드 번호를 출력한다. 만약 서로 대결하지 않을 때는 -1을 출력한다.

김지민은 N명이 참가하는 스타 토너먼트에 진출했다. 토너먼트는 다음과 같이 진행된다. 일단 N명의 참가자는 번호가 1번부터 N번까지 배정받는다. 그러고 난 후에 서로 인접한 번호끼리 스타를 한다. 이긴 사람은 다음 라운드에 진출하고, 진 사람은 그 라운드에서 떨어진다. 만약 그 라운드의 참가자가 홀수명이라면, 마지막 번호를 가진 참가자는 다음 라운드로 자동 진출한다. 다음 라운드에선 다시 참가자의 번호를 1번부터 매긴다. 이때, 번호를 매기는 순서는 처음 번호의 순서를 유지하면서 1번부터 매긴다. 이 말은 1번과 2번이 스타를 해서 1번이 진출하고, 3번과 4번이 스타를 해서 4번이 진출했다면, 4번은 다음 라운드에서 번호 2번을 배정받는다. 번호를 다시 배정받은 후에 한 명만 남을 때까지 라운드를 계속 한다.

마침 이 스타 대회에 임한수도 참가했다. 김지민은 갑자기 스타 대회에서 우승하는 욕심은 없어지고, 몇 라운드에서 임한수와 대결하는지 궁금해졌다. 일단 김지민과 임한수는 서로 대결하기 전까지 항상 이긴다고 가정한다. 1 라운드에서 김지민의 번호와 임한수의 번호가 주어질 때, 과연 김지민과 임한수가 몇 라운드에서 대결하는지 출력하는 프로그램을 작성하시오.

 

문제 이해를 위한 토너먼트 대결 구성 그림

 

---

풀이

import sys
input = sys.stdin.readline

n, j, h = map(int, input().split())  #참가자의 수 N, 김지민의 번호 J, 임한수의 번호 H
num_list = list(range(1, n+1)) #1부터 n까지의 숫자 리스트 생성
num_list[j-1] = 'J' # 김지민의 번호에 해당하는 숫자를 'J'로 표시
num_list[h-1] = 'H' # 임한수의 번호에 해당하는 숫자를 'H'로 표시
cnt = 1
end = True

while end:
    a = []  # 매 루프마다 a 리스트 초기화
    for i in range(0, len(num_list), 2): 
        a.append(num_list[i:i + 2]) # 리스트의 원소를 두 개씩 묶어서 num_list에 다시 담음
    num_list = a

    for index, k in enumerate(num_list):
      if (k == ['J', 'H'] or k == ['H', 'J',]): # 만약 김지민과 임한수가 만났다면,
          print(cnt)
          end = False
          break  # 찾았으면 cnt를 출력하고, 루프를 종료
      elif 'J' in k: # 해당 대결에 김지민이 참여했다면, 
        num_list[index] = 'J'
      elif 'H' in k: # 해당 대결에 임한수가 참여했다면, 
        num_list[index] = 'H'
      else:
          num_list[index] = index + 1

    cnt += 1  # cnt를 증가시켜 라운드 수를 카운트

 

접근 방법

1. 1부터 n까지의 숫자 리스트 생성
2. 주어진 지민, 한수의 번호에 맞는 원소를 J, H로 바꿈 ex) [1, 2, 3, J, 5, H, 7]
3. 숫자 리스트의 원소를 두 개씩 묶음 ex) n이 8일 경우, [[1, 2], [3, 4], [5, 6], [7, 8]] n이 9일 경우, [[1, 2], [3, 4], [5, 6], [7, 8], [9]]
4. 리스트의 원소를 검사하면서 [’J’, ‘H’]이거나 ['H', 'J',]이면 결과를 프린트하고 루프를 종료 만약 J가 존재하는 리스트라면 해당 원소를 J로, H가 존재하는 리스트라면 해당 원소를 H로, 그냥 숫자로만 이루어진 리스트라면 숫자로 바꿈

---

브루트포스(brute force)

brute: 무식한, force: 힘   → 무식한 힘 알고리즘..

 

브루트포스 알고리즘은 가능한 모든 경우를 시도해보는 무차별 대입 방식의 알고리즘이다.

주어진 문제를 해결하기 위해 모든 가능한 조합을 시도해보는 방법으로, 비교적 간단하고 직관적인 접근법이지만, 경우에 따라 많은 시간과 계산이 필요할 수 있기 때문에 효율적이지는 않을 수 있다.

 

1. 완전탐색 알고리즘
2. 가능한 모든 경우의 수를 모두 탐색하면서 요구조건에 충족되는 결과만을 가져온다.
3. 이 알고리즘의 강력한 점은 예외 없이 100%의 확률로 정답만을 출력한다.

• 일반적 방법으로 문제를 해결하기 위해서는 모든 자료를 탐색해야 하기 때문에 특정한 구조를 전체적으로 탐색할 수 있는 방법을 필요로 한다.
• 알고리즘 설계의 가장 기본적인 접근 방법은 해가 존재할 것으로 예상되는 모든 영역을 전체 탐색하는 방법이다.

 

문제해결 방법

① 주어진 문제를 선형 구조로 구조화한다.

② 구조화된 문제공간을 적절한 방법으로 해를 구성할 때까지 탐색한다.

③ 구성된 해를 정리한다.

---

참고 링크

알고리즘 기법[전체 탐색] - 브루트 포스(brute force)