Vienna sausage

비엔나 소시지 IT 블로그

백준 10974번 - 모든 순열

모든 순열 문제 바로 가기

baekjoon 알고리즘 문제 풀이
문제:
N이 주어졌을 때, 1부터 N까지의 수로 이루어진 순열을 사전순으로 출력하는 프로그램을 작성하시오.
입력
첫째 줄에 N(1 ≤ N ≤ 8)이 주어진다.
출력
첫째 줄부터 N!개의 줄에 걸쳐서 모든 순열을 사전순으로 출력한다.

풀이 코드


n = int(input())
num_list = [i for i in range(1,n+1)]
visited = [False] * n
answer = []

def dfs():
    if len(answer) == n:
        print(*answer)
        return
    for i in range(n):
        if not visited[i]:
            visited[i] = True
            answer.append(num_list[i])
            dfs()
            answer.pop()
            visited[i] = False
dfs()

해결 전략:

  1. 1부터 N까지 숫자를 리스트로 만든다. (예: [1, 2, 3])
  2. 각 숫자를 “사용했는지” 체크할 리스트(visited)를 만든다.
  3. 재귀(DFS)로 숫자를 하나씩 선택해 answer에 저장한다.
  4. answer의 길이가 N이 되면 하나의 완성된 순열 → 출력
  5. 한 단계 위로 되돌아가며(pop(), visited=False) 다른 조합 탐색

코드 동작

단계 answer visited 동작
1 [] [F, F, F] 시작
2 [1] [T, F, F] 1 선택
3 [1, 2] [T, T, F] 2 선택
4 [1, 2, 3] [T, T, T] 출력 → 1 2 3
5 [1, 2] [T, T, F] 3 제거 (pop)
6 [1, 3] [T, F, T] 다른 조합 탐색
… … … 반복
마지막 [3, 2, 1] [T, T, T] 모든 경우 출력 완료

answer.pop()과 visited[i] = False

처음에는 이 두 줄이 왜 필요한지 정말 헷갈렸다.
분명히 이미 한 번 넣은 숫자(append)인데, 왜 다시 빼야 하고(pop()),
이미 방문했다고 표시한 걸(visited[i] = True) 왜 또 False로 돌리는 걸까?

이걸 이해하려면 백트래킹(Backtracking) 의 핵심 구조를 알아야 한다.

  • append() : 숫자를 하나 선택해 현재 순열(answer)에 넣는다.
  • dfs() : 그 선택을 기반으로 다음 깊이로 들어간다.
  • pop() : 한 단계의 탐색이 끝나면, 마지막으로 넣은 숫자를 빼서 이전 상태로 되돌린다.
  • visited[i] = False : 방금 사용했던 숫자를 “다시 쓸 수 있다”고 표시한다.