줄다리기

문제 설명

인원이 주어지고, 그 인원 중에서 서로 사이가 좋지 않은 인원의 쌍이 리스트로 주어진다.

사이가 좋지 않은 인원이 이웃하는 경우 좋은 경기력이 나오지 않기 때문에

일렬로 세우는 경우에서 사이가 좋지 않은 인원이 이웃하지 않도록 하는 경우의 수를 구하는 문제다.

접근 방식

• 문제에서 제시한 7명을 일렬로 세우는 경우의 수는 7!인데, 이 중에서 사이가 좋지 않은 학생들이 이웃하지 않도록 세우는 경우를 고려하면 된다.
• 모든 경우의 수 - 이웃한 경우의 수를 수행할 수도 있지만, 다음과 같은 상황에서 효율이 좋지 않다.
• [1,3]이 사이가 좋지 않은 경우, 1 3 X X X X X 의 모든 경우를 확인하는 과정이 불필요하게 존재한다.
• [1, 3]이 사이가 좋지 않은 경우 1 3 X X X X X와 3 1 X X X X X의 경우를 애초에 고려하지 않도록 코드를 작성하여, 효율성을 확보한다.
• 마지막에 서있는 친구와 새로 들어갈 친구의 사이를 확인하고 들어가도록 한다.
• 이를 위해 2차원 리스트를 선언하고 [1][3], [3][1]에 사이가 좋지 않음의 표시인 1을 대입한다.

작성한 코드

def solution(fight):
    global cnt	# 전역 변수 설정
    cnt = 0
    check = [[0] * 8 for _ in range(8)] # 사이 좋은지 확인을 위한 2차원 배열
    ch = [0] * 8						# 숫자 사용 체크용 배열 

    for a, b in fight:
        check[a][b] = 1					# 사이 안좋음 표시
        check[b][a] = 1

    dfs(0, [], check, ch)
    
    return cnt

def dfs(L, res, check, ch):
    global cnt
    if L == 7:							# 일렬로 세워진 경우
        cnt += 1
    else:
        for i in range(1, 8):
            if res and check[res[-1]][i] == 1:	# 마지막 친구와 사이가 안좋은 경우
                continue
            if ch[i] == 0:						# 사용 안한 숫자인 경우
                ch[i] = 1
                res.append(i)
                dfs(L+1, res, check, ch)
                ch[i] = 0						# 사용 안함 처리
                res.pop()