소풍

GitHub - Seungkyu-Han/PS_strategy: 알고리즘 분류하는 워크플레이스

이전에도 풀었던 문제이지만 알고리즘을 복습하면서 다시 풀어보았다.

백준을 위해서 푼 건 아니지만 백준에 문제가 있기는 하다.

2026번: 소풍

요즘 브루투 포스 알고리즘을 풀면서 생각하는 건데 브루트 포스 문제는 백트래킹 기법을 같이 사용해서 푸는 문제가 많은 것 같다.

재귀함수를 이용하다보니 조건을 만족하면 되돌아 오는 백트래킹을 많이 쓰는 것 같다.

덕분에 함수 다루는 실력이 좀 향상된것 같다. ㅎㅎ (지극히 내 생각이다.....)

 

함수를 2개 사용했다.

첫 번째 함수는 현재 있는 멤버에 새로운 친구가 들어갈 수 있는지 확인해주는 함수이다.

# 새로 들어온 친구가 들어갈 수 있는지 확인하는 함수이다.
# 리스트에 첫 번째 인덱스는 0이 있으니 제외하고 시작하자.
def is_friend(plus_friend, member_list):
    for q in member_list[1:]:
        if plus_friend not in friends[q]:
            return False
    return True

굳이 설명할 필요가 없을 거라고 생각된다.

 

두번째 함수는 재귀함수 + 백트래킹 함수 + 탐색 함수이다.

이 함수가 핵심이다.

# cur_cnt는 현재 만들어진 멤버의 수, cur_list는 그 멤버의 번호이다.
def find_friends(cur_cnt, cur_list):

    # 멤버를 K명 모으면 함수를 종료한다. (재귀함수의 기저사례)
    if cur_cnt == K:
        for q in cur_list[1:]:
            print(q)
        return True

    # 순서대로 들어가기 때문에 cur_list에 있는 번호가 가장 큰 멤버는 -1의 인덱스에 있다.
    # 대신 빈 리스트에 -1을 부르면 에러가 뜨기 때문에 이 함수 호출 전에 반복문으로 0을 넣어주고 시작한다.
    for q in range(cur_list[-1] + 1, N + 1):
        if is_friend(q, cur_list):
            cur_list.append(q)
            if find_friends(cur_cnt + 1, cur_list):
                return True
            cur_list.pop()
    return False

우선 함수가 종료되는 조건은 멤버의 수가 K가 되는 조건이다.

글을 작성하면서 생각해보니 굳이 cur_cnt를 쓰지 않고 len함수를 이용해서 인수를 하나 줄일 수 있었을 것 같다.

 

아래 반복문은 아직 확인하지 않은 값을 is_friend로 확인하면서 가능하다면 해당 멤버를 추가해 다시 함수를 호출하는 부분이다.

백트래킹에서 사용하듯이 만약 해당 값으로 답을 찾을 수 없다면 다 확인해본 후에 pop등을 이용해서 값을 빼주어야 한다.

import sys

K, N, F = map(int, sys.stdin.readline().split())

friends = [[] for i in range(N + 1)]

for i in range(F):
    a, b = map(int, sys.stdin.readline().split())
    friends[a].append(b)
    friends[b].append(a)


# 새로 들어온 친구가 들어갈 수 있는지 확인하는 함수이다.
# 리스트에 첫 번째 인덱스는 0이 있으니 제외하고 시작하자.
def is_friend(plus_friend, member_list):
    for q in member_list[1:]:
        if plus_friend not in friends[q]:
            return False
    return True


# cur_cnt는 현재 만들어진 멤버의 수, cur_list는 그 멤버의 번호이다.
def find_friends(cur_cnt, cur_list):

    # 멤버를 K명 모으면 함수를 종료한다. (재귀함수의 기저사례)
    if cur_cnt == K:
        for q in cur_list[1:]:
            print(q)
        return True

    # 순서대로 들어가기 때문에 cur_list에 있는 번호가 가장 큰 멤버는 -1의 인덱스에 있다.
    # 대신 빈 리스트에 -1을 부르면 에러가 뜨기 때문에 이 함수 호출 전에 반복문으로 0을 넣어주고 시작한다.
    for q in range(cur_list[-1] + 1, N + 1):
        if is_friend(q, cur_list):
            cur_list.append(q)
            if find_friends(cur_cnt + 1, cur_list):
                return True
            cur_list.pop()
    return False


if not find_friends(0, [0]):
    print(-1)

이 문제의 전체코드이다.

import sys

K, N, F = map(int, sys.stdin.readline().split())

friend = {i+1: [] for i in range(N)}

for i in range(F):
    first, second = map(int, sys.stdin.readline().split())
    friend[first].append(second)
    friend[second].append(first)


def judge(plus_friend, members):
    for per in members:
        if per not in friend[plus_friend]:
            return False
    return True


def backtracking(per_cnt, cur_members):
    if per_cnt == K:
        for i in cur_members:
            print(i)
        exit(0)

    for i in range(cur_members[-1] + 1, N + 1):
        if judge(i, cur_members):
            backtracking(per_cnt + 1, cur_members + [i])

for i in range(1, N):
    backtracking(1, [i])

print(-1)

전에 풀었던 코드인데 재귀함수를 빠져나올 방법을 찾지 못해서 그냥 exit로 프로그램을 종료해버렸었다.

물론 이렇게 풀어도 되기는 하지만 재귀함수, 백트래킹을 제대로 사용하기 위해 함수를 빠져 나올 수 있는 방법을 생각하며 풀어야겠다.