문제를 처음 접할 경우, 너무 쉬운게 아닐까라고 생각해 볼 수 있는 문제지만, 나름의 복잡함을 확인할 수 있는데, 일단 입력 부분이다. 나라마다 승/무/패의 결과가 일렬로 나열되어 주어지기 때문에 나라별로 정리할 필요가 있다. 리스트 슬라이싱 등 여러가지 방법이 있을 수 있지만, 아래와 같이 map iterator를 이용해서 정리하면 비교적 깔끔하게 정리가 가능하다.
n을 map 객체로 선언한 후, next(n)의 경우는 iterator에서 하나씩 item을 꺼내주는 함수이므로 이를 이용해서 승/무/패 3개씩 6개의 독립 리스트로 분리할 수 있다.
n = map(int, readl().split())
result = [[next(n) for w in range(3)] for t in range(6)]
그런 다음 문제는 어떤식으로 접근해야 할까. 일단 경우의 수를 생각해 보는 것이 중요하다.
일단 나라별로 나머지 5나라와 시합을 진행해야 하는 경우의 수를 세어 보는 것이다. 6개 나라 중에서 2개 나라씩 매칭으로 조합을 생각해 보면,
# 0번국가 부터 5번 국가까지 모두 매칭해 보면 총 15가지 경우의 수가 나온다.
match_game = ((0,1),(0,2),(0,3),(0,4),(0,5),(1,2),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5))
모든 알고리즘의 시작은 전탐색이다. 모든 경우를 생각해 보면, 15가지 시합에 대해서 양쪽팀이 (승/패), (무/무), (패/승)의 3가지 경우가 나오기 때문에 모든 경우를 탐색하기 위해서는
기본적으로 아래와 같이 간단하게 경기가 성립되지 않는 경우를 제외해 주면 도움이 된다. 한국가의 경기 수가 5번이 되지 않는 경우, 전체 게임의 승수와 패배수가 같지 않은 경우, 무승부의 개수가 홀수인 경우 등이 그것이다.
def check():
win, lose, draw, draw_count = 0, 0, 0, 0
for match_result in result:
if sum(match_result) != 5: return False # 한 국가가 5번의 경기를 하지 않으면 잘못된 경기
win += match_result[0]
lose += match_result[2]
draw += match_result[1]
if win != lose: return False #승수와 패배수가 같지 않으면 잘못된 경기
if (draw % 2) == 1: return False # 무승부 개수가 홀수이면 잘못된 경기
return True
위의 check로 모든 것을 다 체크할 수는 없다. 위의 조건을 만족하면서도 국가간의 매칭이 잘 이루어 지지 않는 경우가 존재하기 때문이다. 승과 패가 한쪽으로 치우쳐져 있는 경우가 그렇다. 예를 들자면, 아래와 같은 경우다. check함수의 모든 조건을 만족하면서도 하나씩 따져보면 말이되지 않는다. 승-패가 매칭이 되지 않기 때문이다. 적어도 3나라가 2패 이상을 해야 하는데, 2패 이상인 나라는 2개 밖에 없다.
| 승 | 무 | 패 | |
| A 국가 | 1 | 4 | 0 |
| B 국가 | 3 | 1 | 1 |
| C 국가 | 0 | 2 | 3 |
| D 국가 | 1 | 4 | 0 |
| E 국가 | 0 | 2 | 3 |
| F 국가 | 3 | 1 | 1 |
따라서, 전탐색을 진행해야 한다. 모든 경우를 탐색해 보는 방법은 어떻게 할 수 있을까? iterative한 방법(for 문 사용) 으로 풀어나갈 수 있을까? 가능할지 모르겠지만, 가지를 치는 경우와 배열 조작 및 복구 문제가 복잡해 질 수 있다. 그렇다면? 경우의 수가 15개 정도 이므로 dfs를 통해서 확인해 볼 수 있다. 기본적인 접근법은 주어진 case에서 모든 경우의 수를 recursive하게 탐색해 나가는 것인데, 가지치기를 쉽게 하기 위해서 주어진 입력값에서 매칭(승/무/패)에 해당되는 내용의 경우수를 빼나가는 것이 유리하다. 승/무/패 테이블에서 0보다 작아지는 경우는 불가능 하므로 이 경우를 제외하고 진행한다는 의미이다.
def dfs(num):
if num == len(match_game):
return True
for i in range(3):
if (test[match_game[num][0]][i] < 1) or (test[match_game[num][1]][2-i] < 1): continue
test[match_game[num][0]][i] -= 1
test[match_game[num][1]][2-i] -= 1
if dfs(num+1): return True
test[match_game[num][0]][i] += 1
test[match_game[num][1]][2-i] += 1
return False
총 4가지 케이스에 대해서 결과만 리스트로 뽑아주어 출력하면 알고리즘 풀이 성공이다.
'알고리즘 > DFS' 카테고리의 다른 글
| [DFS] 그래프 단절점, 단절선 (0) | 2023.09.23 |
|---|---|
| [DFS] BJ_13023, ABCDE (0) | 2023.02.23 |
