[백준] 1327. 소트 게임
⏱️ 소요시간
1시간 반. 이 문제를 보고 BFS인지 DFS인지의 판단이 늦었습니다.
📚 문제 요약
[백준] 1327. 소트게임
1부터 N까지 정수로 이루어진 순열이 주어지고 숫자 K가 주어졌을 때 어떤 수를 기준으로 오른쪽의 K개의 수를 뒤집어나가며 오름차순으로 만들 수 있는 경우, 최소 몇 개의 수를 택하면 되는지 횟수를 출력, 오름차순으로 만들 수 없다면 -1 출력
📑 풀이 요약
문제에서 최소 몇 개의 수를 택하면 되는지 묻고 있기 때문에 너비 우선 탐색임을 알아야 하며 BFS로 풀이를 해야겠다고 생각했어야 했다!
나는 DFS를 이용하여 내가 탐색하는 노드가 유망하지 않은 경우 (= 이미 탐색이 완료된 경우) 되돌아가는 백트래킹을 생각했으나, 모든 노드를 깊게 파지 않고 너비 우선 탐색으로 코드를 작성하면 된다.
DFS와 BFS를 구분하는 것이 중요한데 구분하는 기준이 무엇일까.
그래프의 탐색 과정을 떠올리며 구분해보자
1. DFS
DFS인 경우 한 번 탐색을 시작할 때 어떠한 점을 잡고 이 경로로 가는게 맞는지 아닌지 전부 다 탐색하는 방식이다.
2. BFS
BFS의 경우 한 점에서 시작해서 깊이마다 탐색하는 특징이 있다. 0에서 1, 0에서 2, 0에서 4, 그 다음에 1에서 갈 수 있는 곳 없으니 pass, 2에서 3, 4에서 갈 수 있는 곳 없으니 pass 이런 식으로!
이 문제는?
이런식으로 단계별로 가능한지 체크하고 그 다음 단계로 넘어가기에 BFS로 풀어야 한다.
💡 결론 : BFS와 DFS
BFS 선택 기준
- 깊이 특징을 이용한 문제, 대표적으로 최단거리
- 왜? 모든 깊이(단계)마다 가능한 경우를 모두 탐색하고 답이 없는 경우 다음 단계로 넘어간다. 모든 단계를 확인하고 다음 단계를 확인하기에 탐색중에 정답을 발견하면 그게 최단거리가 될 수밖에 없다!
DFS 선택 기준
- 모든 경우를 하나씩 전부 탐색해야 하는 경우
- 조합, 순열
🖥️ 제출 코드
from collections import deque
import copy
n, k = map(int, input().split())
arr = list(map(int, input().split()))
que = deque([(arr, 0)]) #array, cnt
visited = set([tuple(arr)])
print(visited)
flag = False
def isSort(array):
for i in range(n-1):
if array[i] <= array[i+1]:
continue
else:
return False
return True
def reverse(array, idx):
a = array[:]
for i in range(k//2):
a[idx+i], a[idx+k-1-i] = a[idx+k-1-i], a[idx+i]
return a
while que:
array, cnt = que.popleft()
print(array, cnt)
if isSort(array):
print(cnt)
flag = True
break
for idx in range(n-k+1): #n-k까지
a = reverse(array, idx) #뒤집을 배열과 시작인덱스
if tuple(a) not in visited:
que.append((a, cnt+1))
visited.add(tuple(a))
#print("que:", que, "visited", visited)
if not flag:
print(-1)