취준생의 코딩테스트 연습기

[백준] 15650번 N과 M(2) / 파이썬(python) 본문

코딩테스트/백준

[백준] 15650번 N과 M(2) / 파이썬(python)

Jiwon_C 2021. 3. 12. 03:18

# 문제 링크

www.acmicpc.net/problem/15650

 

15650번: N과 M (2)

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해

www.acmicpc.net

# 관련 알고리즘 이론

jiwon-coding.tistory.com/34

 

백트래킹 (Backtracking)

# 백트래킹 (퇴각 검색) - 길을 가다가 이 길이 아닌 것 같으면 왔던 길로 되돌아가 다른 경로로 진행 - 보통 재귀로 구현하며 조건이 맞지 않으면 종료한다. - DFS(깊이 우선 탐색) 기반 # EXAMPLE  -

jiwon-coding.tistory.com

# Soultion

15649번과 거의 동일하지만 이 문제에서는 [1,2], [2,1]과 같은 경우는 중복되는 경우로 보고 [1,2]만 출력해야한다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# 15649
n,m = list(map(int,input().split()))
= []
def dfs():
    if len(s)==m:
        print(' '.join(map(str,s)))
        return
    
    for i in range(1,n+1):
        if i not in s:
            s.append(i)
            dfs()
            s.pop()
dfs()
 
cs

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 15650번
n,m = list(map(int,input().split()))
= []
def dfs(start):
    if len(s)==m:
        print(' '.join(map(str,s)))
        return
    
    for i in range(start,n+1):
        if i not in s:
            s.append(i)
            dfs(i+1)
            s.pop()
dfs(1)
 
    
cs

 

4. 소스를 보면 알수있듯이 15649번과 동일하지만, start 변수만 추가를 해주었다.

8. 기존에는 1부터 n까지 모든 숫자를 사용했지만 [2,1]과 같이 앞의숫자가 뒤의숫자보다 작은경우를 제외하기위해 start부터 n까지 숫자를 사용한다.

12. 재귀함수를 호출할때는 i를 이용하여 자신의 다음숫자를 부르게된다.

 

 


동작과정을 간단하게 표현해봤습니다.

7 Comments
  • 프로필사진 브루노 2021.07.01 10:46 안녕하세요 코드도 읽기 쉽게 써주시고 설명까지 자세하게 해주셔서 감사합니다!
    15650번 조금 이해가 안 되는 부분이 있어서 질문드리고 싶어서 글 남겨요
    n = 3 m = 2라면
    처음에 s에 1을 추가하고 2를 추가한 후에 dfs(3)이 될때 s에 [1,2]가 저장되는게 맞나요?
    어느정도 이해는 했는데 제가 코딩 초보라서 안에서의 자세한 과정이 이해가 잘 안 되네요ㅠ
    혹시 설명 가능하시다면 설명 좀 부탁드려요~
  • 프로필사진 Jiwon_C 2021.07.01 16:41 신고 동작과정을 간단하게 표현한걸 글에추가했어요! 그래도 이해안가시면 다시 말씀해주세용
  • 프로필사진 브루노 2021.07.01 15:02 #15650
    12번째 줄 dfs(i+1)을 dfs(i)로 해도 정답처리 되던데 어떤 차이점이 있는지 아시나요??
  • 프로필사진 Jiwon_C 2021.07.01 16:17 신고 dfs(i)를 하게되면 s=[1] i=1과 같이 동일한 숫자도 확인을 하게되는데, 10번째 줄에서 중복체크를 하기때문에 결국 i=1은 s에 넣지않게되므로 동일한 결과가 나옵니다!
    결론적으로 동일한 값이나오지만, dfs(i)를 하게되면 하지않아도 되는 재귀함수를 한번 더 하게되므로 dfs(i+1)을 사용하는게 좋을 것 같아요!
    이해가 되셨으면 좋겠네요..ㅠㅠ
  • 프로필사진 Jiwon_C 2021.07.01 16:22 신고 댓글을 달면서 저의 소스에 문제점을 발견했네요!
    dfs(i+1)을 하게된다면 10번째 줄에서 중복체크를 하는 부분은 없어도 됩니다ㅎㅎㅎ
    브루노님이 말씀하신 것처럼 dfs(i)를 하게된다면 필요한 if문이네요
    감사합니다!
  • 프로필사진 SeongOnion 2022.01.14 17:33 신고 숫자가 1부터 N까지 정렬된 상태로 들어가기 때문에 dfs함수의 for문 안에 있는 if i not in s의 로직은 삭제해도 무방하네요. 어차피 i는 순차적으로 들어가기 때문에.. 좋은 풀이 잘 보고 갑니다!
  • 프로필사진 happy_life 2022.03.07 13:43 신고
    코드는 비슷한데 arr = sorted(arr) 이라는 조건으로 간단하게 푼 제 코드 어떤가요!

    N,M = map(int,input().split())
    check_list = [False] * N
    arr = []

    def dfs(count):
    #깊이 탐색 완료 시
    if(count == M and arr == sorted(arr)):
    print(*arr)

    for i in range(N):
    #수열이므로 중복은 제거하는 조건
    if(check_list[i]):
    continue

    #자기보다 작은건 안된다는 조건


    check_list[i] = True
    arr.append(i+1)

    #depth 추가
    dfs(count+1)

    #초기화
    check_list[i] = False
    arr.pop()

    dfs(0)
댓글쓰기 폼