(JAVA) 백준 6987번 : 월드컵 --- [백트래킹]

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

6987번: 월드컵

 

안녕하세요.

 

이 문제는 백트래킹 + 완전탐색 + 브루트 포스 가 합쳐진 난이도가 있는 문제입니다.

 

 

처음에 간단하게 조건을 하나하나 추가해가면서 풀다보니 계속 틀렸는데요..

 

 

http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1114&sca=4030

JUNGOL

정골가서 왜틀렸는지 테스트케이스를 보려고 몇 번이고 돌리면서 수정했었지만

 

결국 처음 코딩했던 알고리즘을 버리고

 

백트래킹 측면에서 좀 더 단순하게 생각했습니다. (조금 다른 사람 해설을 참고했습니다..!)

 

 

 

 

핵심은

  -  총 6개의 팀이 있으며, 한 팀당 무조건 5번 경기를 해야 합니다. (6번이거나, 4번만 한 경우는 무조건 불가능)

 

  -  한 번 경기한 팀이랑은 두 번 다시 경기를 하지 않습니다. 즉, A - B 경기했으면, B - A 경기는 절대 없습니다.

 

  -  두 팀이 경기를 펼쳐서 나온 결과는 총 3가지가 있습니다.

 

 

ex) A, B 두 팀이 있다고 했을 때, 

 

A - 승 / B - 패

A - 무 / B - 무

A - 패 / B - 승

 

총 3가지 입니다.

 

 

그럼 이어서,

   

  -  총 경기 수는 15경기 입니다. 

 

A - B, C, D, E, F

B - C, D, E, F

C - D, E, F

D - E, F

E - F

 

 

  -  백트래킹 시, A - 승 / B - 패 일 경우, 각각의 결과 횟수를 1씩 뺀 후 다음 경기를 위한 백트래킹 함수를 재귀호출 합니다. 그 다음, 다시 결과 횟수를 원상복귀합니다.

  *** 당연히, 전제 조건은 두 팀 다 해당 결과에 대한 횟수가 최소 1 이상은 있어야 합니다. 결과가 0이면 이 팀이 이겼는지 졌는지 알 수 없으니까요!

 

  -  그래서 백트래킹 함수에서 최종 success 조건은 경기 횟수로 판단합니다. 즉, 경기 횟수가 15경기를 채울 수 있는지 없는지로 판단합니다.

 *** 자세한 사항은 하단 소스코드를 확인해주세요.

 

 

시간 복잡도는 대략 O(3^15) 입니다. (한 경기당 최대 3가지 경우의 수가 존재하고, 총 15경기니까)

 

사실, 문제의 난이도는 크게 높지 않다고 생각합니다. 잘 읽힐 뿐더러 어떻게 해결해야할지 감이 오거든요.

 

하지만, 조금 더러운 면이 없지않아 있습니다. 브루트 포스 같은 것도 있어서 코드도 길어지고, 때려박는 느낌도 있습니다.

 

 

매커니즘은 위 핵심을 파악하면 어려운 부분은 없다고 생각하기에,

좀 더 알고싶으시다면 하단 소스코드 및 주석을 확인해주시면 될 것 같습니다.

 

 

감사합니다.

 

 

 

 

소스코드

---