문제
https://www.acmicpc.net/problem/15649
문제 풀이
해당 문제는 백트래킹 알고리즘을 활용하여 풀 수 있다.
백트래킹 알고리즘은 모든 가능한 경우의 수를 탐색하면서 조건에 맞지 않는 경우는 더 이상 탐색하지 않고 이전 상태로 돌아가는 방식
소스코드
def backtracking(n,m,selected,visited): #selected : 현재까지 선택된 수열 나타내는 리스트
# 수열의 길이가 m과 같아지면 selected 리스트의 내용을 출력하고 함수 종료
if len(selected) == m:
print(' '.join(map(str,selected)))
return
for i in range(1,n+1):
# 1부터 n까지의 숫자 중에서 방문하지 않은 숫자를 하나씩 선택
# 선택된 숫자를 selected 리스트에 추가하고, 방문으로 표시
if not visited[i]:
visited[i] = True
selected.append(i)
# 재귀적으로 다음 숫자를 선택하기 위해 backtracking 함수 호출
backtracking(n,m,selected,visited)
# 재귀 호출이 종료되면 선택한 숫자를 selected 리스트에서 제거하고
# 해당 숫자를 방문하지 않았다고 표시 (다음으로 넘어가기 위함)
selected.pop()
visited[i] = False
n,m=map(int,input().split())
s=[] # 숫자가 쌓일 스택
visited = [False] * (n+1) #방문 여부를 나타내는 리스트 visited 정의
backtracking(n, m, [], visited)
✅ ' '.join(map(str,selected)) 의 역할
print(' '.join(map(str, selected))) 구문은
선택된 수열(selected)을 공백으로 구분하여 출력하기 위한 코드
map(str, selected)
: selected 리스트의 각 요소를 문자열로 변환
' '.join(...)
: map 함수를 통해 변환된 문자열 요소들을 공백으로 구분하여 하나의 문자열로 결합
join 메서드는 인자로 전달된 리스트(또는 이터러블)의 요소들을 하나의 문자열로 연결하는 역할
공백 문자열 ' '을 구분자로 사용하여 요소들을 연결한다.
예를 들어, selected 리스트가 [1, 2, 3]인 경우,
map(str, selected)는 ['1', '2', '3']을 반환
그리고 ' '.join(['1', '2', '3'])은 '1 2 3'을 반환
마지막으로, print('1 2 3')은 '1 2 3'을 콘솔에 출력
따라서, print(' '.join(map(str, selected))) 구문은 선택된 수열을 공백으로 구분하여 출력하는 역할
UXUI Designer