GitHub - Seungkyu-Han/PS_strategy: 알고리즘 분류하는 워크플레이스
알고리즘 분류하는 워크플레이스. Contribute to Seungkyu-Han/PS_strategy development by creating an account on GitHub.
github.com
이전에도 풀었던 문제이지만 알고리즘을 복습하면서 다시 풀어보았다.
백준을 위해서 푼 건 아니지만 백준에 문제가 있기는 하다.
2026번: 소풍
만약 K명의 친구 관계인 학생들이 존재하지 않는다면 -1을 출력한다. 그 외의 경우에는, K개의 줄에 학생들의 번호를 증가하는 순서로 한 줄에 한 개씩 출력한다. 여러 경우가 존재한다면 첫 번째
www.acmicpc.net
요즘 브루투 포스 알고리즘을 풀면서 생각하는 건데 브루트 포스 문제는 백트래킹 기법을 같이 사용해서 푸는 문제가 많은 것 같다.
재귀함수를 이용하다보니 조건을 만족하면 되돌아 오는 백트래킹을 많이 쓰는 것 같다.
덕분에 함수 다루는 실력이 좀 향상된것 같다. ㅎㅎ (지극히 내 생각이다.....)
함수를 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로 프로그램을 종료해버렸었다.
물론 이렇게 풀어도 되기는 하지만 재귀함수, 백트래킹을 제대로 사용하기 위해 함수를 빠져 나올 수 있는 방법을 생각하며 풀어야겠다.
'알고리즘 > 브루트포스' 카테고리의 다른 글
| 백준 4675 셀프 넘버 (1) | 2024.01.15 |
|---|---|
| 백준 1065 한수 (0) | 2024.01.15 |
| 게임판 덮기 (0) | 2022.09.17 |
| 보글 게임 (1) | 2022.09.16 |
| 조합을 구하는 알고리즘 (0) | 2022.09.15 |
