[SWEA/D3] 6808 규영이와 인영이의 카드게임 / 백트래킹

문제 바로가기

SW Expert Academy

나의 코드 및 설명

def dfs(count,gy,iy):
    global gy_win, gy_lose
    if count == 9: #9개를 다 뽑았다면,
        #규영의 총점과 인영의 총점을 비교
        if gy>iy: 
            gy_win += 1
        if gy<iy:
            gy_lose += 1
        return
    for i in range(len(iy_list)):
        if v[i] == 0: #중복하여 카드를 뽑는 것을 막기위한 방문처리
            v[i] = 1
            #규영이가 뽑은 0~8번 인덱스의 카드와 인영이가 무작위로 뽑은 카드를 비교 
            if gy_list[count] > iy_list[i]:
                next_gy = gy+gy_list[count]+iy_list[i]
                next_iy = iy
            elif gy_list[count] < iy_list[i]:
                next_gy = gy
                next_iy = iy+gy_list[count]+iy_list[i]
            dfs(count+1, next_gy, next_iy)
            v[i] = 0

t = int(input())
for test_case in range(1,t+1):
    gy_list = list(map(int, input().split()))
    iy_list = []
    for i in range(1,19):
        if i not in gy_list:
            iy_list.append(i)
    v = [0] * 9
    gy_win = 0
    gy_lose = 0
    dfs(0,0,0)
    print("#{} {} {}".format(test_case, gy_win, gy_lose))

피드백

SWEA에는 파이썬으로 제출할 수 없게 되었다. 하지만 문제가 너무 괜찮아보여서 한 번 풀어봤다. 백트래킹으로 비교적 간단하게 구현했는데, 처음에는 좀 헤맸다. 규영이의 카드는 0번 인덱스부터 8번 인덱스까지 순차적으로 뽑아야 하고, 인영이의 카드는 중복을 제외하고 무작위로 뽑아야 되는데, 규영이가 뽑은 카드의 인덱스와 인영이가 뽑은 카드의 인덱스를 같게 해버리는 바람에 계속 잘못된 값이 출력되었다. 인영이가 뽑은 카드와 비교할 규영이의 카드의 인덱스를 count로 주니까 맞을 수 있었다.