[Python] 백준 온라인 저지 15649 N과 M(1)

목차

문제

---

https://www.acmicpc.net/problem/15649

15649번: N과 M (1)

 

설계&풀이

---

백트래킹의 기본문제다.
매번 DFS/BFS를 도망만 다녔다가 각잡고 제대로 공부해보고자.. N과M 시리즈를 시작해봤다.

요건은 간단하다.

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
- 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열

백트래킹이란걸 아는 상태에서 DFS를 적용해보려고 했는데, 도저히 감이 안잡혀서 풀이를 보고 다시 풀어보는 방식으로 진행했다.

먼저 기본적인 입력 틀을 만들어준다.

n, m = map(int, input().split())
s = []
visited = [False] * (n+1)

s는 m개의 숫자를 저장해놨다가 출력해줄 용도로 사용되고
visited는 DFS에서 자주 사용되는 방문 체크 용도로 사용된다.

N = 4, M = 2일 때를 예로 들어 시뮬레이션 해보자.
일단 답은
(1, 2), (1, 3), (1, 4), (2, 1), (2, 3), (2, 4), (3, 1), (3, 2), (3, 4), (4, 1), (4, 2), (4, 3) 이다.

1.  먼저 첫번째 요소가 1일 때를 찾아본다. 1부터 4까지 탐색한다.
   이 때, 중복 없는 것이 포인트니까 (1, 2)로 만들어야 한다.
2. (1, 2)가 s에 있는지 확인한다.
3. 없다면 해당 값을 출력해주고, 다시 첫번째 요소가 1인 세트를 찾기 위해 탐색한다.
   기존에 2가 있던 자리는 pop해주고 방문한 적이 없는 것으로 처리해준다.
4. 마찬가지로 (1, 3), (1, 4) 쌍을 만들어주고, 1로 시작하는 쌍은 끝내고 2로 시작하는 쌍을 만들기 위해
   visited[2] 로 방문한다. 이 때, 3번에서 visited[2] 를 False 처리해줬기 때문에 여기서 방문이 가능하다.
   이 부분이 뭔가 흐름상으로는 이해가 가는데 코드로는 이해가 안가서 계속 생각했다...
5. 이후로는 동일한 동작으로 2번부터 4번까지 돌면 조합들이 만들어진다.

 

코드 GIT 주소

---

PS_study/1.py at main · kkkapuq/PS_study · GitHub

GitHub - kkkapuq/PS_study: 1일1솔 스터디

 

코드

---

'''
문제 : N과M (1)
난이도 : 실버 3
링크 : https://www.acmicpc.net/problem/15649
'''

n, m = map(int, input().split())
s = []
visited = [False] * (n+1)

def dfs():
    # 만약 s의 길이가 m과 같다면 출력하고 continue
    if len(s) == m:
        print(' '.join(map(str, s)))
        return
    else:
        # 1부터 n까지 탐색하기
        for i in range(1, n+1):
            if not visited[i]:
                visited[i] = True
                s.append(i)
                dfs()
                # m개의 숫자를 다 체크하고 난 뒤에 다음 수가 들어올 자리를 만들어줘야됨
                s.pop()
                # 해당 자리는 방문하지 않은 걸로 하기
                visited[i] = False

dfs()

결과

---

 

 

 

구독 및 하트는 정보 포스팅 제작에 큰 힘이됩니다♡