[DFS/BFS/완전탐색] ▲ 10974번 - 모든 순열(DFS, 완전 탐색)

[백준] 10974번 - 모든 순열

풀이 시간: 20~30분 이내

라이브러리를 사용하지 않는다면 시간이 좀 걸린 문제로 추후 복습 필요!

(풀이1) permutaions 라이브러리 이용

1) 문제 해결 아이디어

파이썬에서 순열을 반환해주는 라이브러리를 이용하면 쉽게 풀 수 있다. 

 

<순열을 출력하는 방법>

1. '구분자'.join(리스트) 이용

join을 이용하면 리스트의 문자들을 구분자로 이어붙여 문자열로 출력할 수 있다.

다만, graph에 담긴 원소들은 문자가 아니라 숫자이므로 map을 이용하여 int→str 형변환한 후 join함수를 사용해야 한다!

2. 2중 for문 이용

 

2) 소스코드

from itertools import permutations

n = int(input())
graph = [i for i in range(1, n + 1)]  # 1 ~ n 

for i in permutations(graph):
  print(' '.join(map(str, i)))
'''
for i in permutations(graph):
  for j in i:
    print(j, end= " ")
  print()
'''

(풀이2) DFS를 이용한 백트래킹

1) 문제 해결 아이디어

하지만 라이브러리를 사용하지 않고 푸는 방법 또한 알고 있을 필요가 있기 때문에 이러한 풀이로도 꼭 풀어봐야 한다. 막상 라이브러리를 사용하지 않고 풀려고 하니 답답했다.

 

깊이 0으로 dfs 호출하고 깊이(depth)가 n이 되면 순열(temp)값을 출력시키고 종료하는 방식이다.

여기서 중요한 점은 1 ~ n 에 대해 for문을 돌면서 현재 선택한 값(i)가 순열(temp)에 없다면 숫자를 넣어주고 (깊이 + 1)로 dfs를 호출한 후 사용한 숫자(i)를 다시 꺼내 주어야 한다는 것이다.

 

2) 소스코드

n = int(input())
temp = []

# DFS
def dfs(depth):
  # 깊이가 n이 되면 종료
  if depth == n:
    print(*temp)
    return

  for i in range(1, n + 1):
    # 아직 사용하지 않은 숫자면
    if i not in temp:
      temp.append(i)  # 사용할 숫자 넣기
      dfs(depth + 1)    # 다음 깊이로 dfs 호출
      temp.pop()      # 사용한 숫자 꺼내기
dfs(0)

[참고] https://honggom.tistory.com/115

[백준] 10974번 문제 (모든 순열) 파이썬(Python) 풀이