[종만북] 소풍

gmelan·2022년 1월 30일
0

알고리즘 트레이닝

목록 보기
1/14

풀어보기

접근

규칙에 맞게 경우의 수를 센다.
1. 항상 서로 친구인 학생들끼리만 짝을 지어 줄 수 있다.
2. 짝이 되는 학생의 일부만 다르더라도 서로 다른 방법이다.

1. 인접 리스트로 저장하고 완전 탐색하기

처음 생각한 방법으로, 친구 관계 그래프를 (방향성이 있는) 인접 리스트 형태로 저장한 후 깊이 우선 탐색을 통해 답을 도출해보았다.

인접 리스트로 자료를 저장하고 이를 단방향으로 탐색하여 같은 쌍이 중복 계산되는 경우를 없애고자 하였으나, 가능한 모든 쌍이 완전하게 탐색되지 않는 경우가 발생하였다.

단방향이 아닌 양방향으로 자료를 저장하고 다음 쌍을 찾기 위한 코드가 추가로 들어가는 등의 수정을 거친 결과, 결국 인접 리스트로 자료를 저장하는 의미가 없어지고 말았다.

...이 쯤에서 코드를 갈아엎고 새로 짜기 시작했다.

2. 관계 행렬로 저장하고 완전 탐색하기

친구 관계 그래프를 방향성이 없는 관계 행렬로 저장하고, 이를 깊이 우선 탐색을 통해 답을 도출하였다.

  • 짝을 찾은 경우 마치 DFS에서의 방문 여부를 저장하는 배열처럼 따로 표시를 해두면 그래프의 방향성 여부와 관계없이 중복되는 경우를 없앨 수 있었다.

  • 또한 이 문제에서 제시되는 자료를 방향 그래프로 저장해버리면 앞서 말했던 모든 항목을 탐색할 수 없는 문제가 발생하여 오히려 곤란해진다는 사실도 발견하였다.

따라서, 새 코드에서는 중복 탐색되는 경우를 없애기 위해 이미 짝을 찾은 친구를 solved_friends에 표시하는 방법을 선택하였다.

코드 2 - 관계 행렬과 방문 여부 배열을 활용한 DFS 구현

from sys import stdin

test_case = int(stdin.readline())

def solve(solved_friends):
    global pairs, n

    next_friend = -1
    for i in range(n):
        if solved_friends[i] == False:
            next_friend = i
            break
    
    if next_friend == -1:
        return 1

    res = 0
    for i in range(next_friend, n, 1):
        if (not solved_friends[i]) and pairs[i][next_friend]:
            solved_friends[i] = solved_friends[next_friend] = True
            res += solve(solved_friends)
            solved_friends[i] = solved_friends[next_friend] = False

    return res


while test_case:
    n, m = map(int, stdin.readline().strip().split())
    pairs = [[False for _ in range(n)] for _ in range(n)]

    PAIRS_RAW = tuple(int(i) for i in stdin.readline().strip().split())
    for i in range(0, len(PAIRS_RAW), 2):
        pairs[PAIRS_RAW[i]][PAIRS_RAW[i + 1]] = True
        pairs[PAIRS_RAW[i + 1]][PAIRS_RAW[i]] = True

    print(solve([False for _ in range(n)]))

    test_case -= 1

결국 책에 있는 해답과 비슷한 코드가 되었고 시사점도 비슷하게 되었다.

  • solve 함수 내 두 번째 반복문에서 다음 짝을 탐색하기 위해 재귀 호출을 하는 부분(20~22번 줄)을 보자. solved_friends의 각 항목을 True로 두고 호출한 후 다시 False로 바꾸는데, 이렇게 하면 DFS에서 추가적인 절차 없이 간단하게 탐색이 가능하다는 장점이 있다.

  • solve 함수에서 반환값을 담을 res를 보자. 이렇게 하면 탐색 결과 짝이 없는 경우 0이, 짝이 있는 경우 그 경우의 수가 반환되어 편리하다.

0개의 댓글