TIL
백트래킹
백트래킹을 쉽게 설명하자면 DFS + 가지치기 이라고 할 수 있다.
백트래킹은 DFS의 과정에서 반복되거나 불필요한 과정을 가지치기로 쳐내서 모든 경우의 수를 탐색하는 DFS의 시간을 줄여주는 알고리즘이다.
즉,
- 유망성(promising)을 따져보고
- 불필요하다 싶으면 가지치기(pruning)을 하는 방식
마음으로는 이해가 되지만 이걸 구현한다고 생각하니 참 막막하기 그지없다. 그렇다고 그냥 넘어갈 수도 없고 애매하게 이해하고 넘어갔다간 브레이크가 없는 재귀함수처럼 공부 할듯하니 완벽하게 이해할 수 있도록 코드를 해부하며 이해해가는 과정을 밟아보려한다.
1번 - 15649
import sys
N, M = map(int, sys.stdin.readline().split())
visited = [False] * N
out = []
def backtracking(depth, n, m):
if depth == m: # 탈출 조건
print(*out) # out의 언패킹
return
for i in range(N): # check 하면서 탐사
if not visited[i]: # visited가 False이면, 즉, 탐사 안했다면
visited[i] = True # 탐사 내용 얻데이트
out.append(i+1) # 탐사 내용 (출력용)
backtracking(depth+1, n, m) # 다음 깊이 탐색
visited[i] = False # 탐사완료 후 빠꾸하기 위해
out.pop() # 재귀함수 내에서 depth == m 이라는 조건을 만족하고 출력하고 나옴
backtracking(0, N, M) 백준의 백츄래킹 시리즈인 N과 M(1) 문제를 활용했다. (15649번)
- 주의해야 하는 포인트는 N과 M의 역할을 헷갈리지 않는 것,
N은 나올 수 있는 숫자이며 탐사 유무를 판단, 해당 값을 할당하는 역할
M은 결과로 나열되는 문자의 길이, 탐색의 깊이, 탈출 조건- 다른 포인트는
visited이라는N의 길이의 리스트를 만들어 탐사 체크리스트로 활용한다는 점- 또 다른 포인트는
visited에True를 할당하고 확인이 끝났을 때 다시False를 할당한다는 점
여기까지의 배움을 바탕으로 다음 문제인 N과 M(2)를 풀어봤다.
2번 - 15650
import sys
N, M = map(int, sys.stdin.readline().split())
visited = [False] * N
out = []
def backtracking(depth, n, m):
if depth == m:
print(*out)
return
for i in range(n):
if not visited[i]:
visited[i] = True
out.append(i+1)
backtracking(depth+1, n, m)
out.pop()
for j in range(i+1, n): # 달라진 부분
visited[j] = False # 윗행의 visited[i] = False 대신
backtracking(0, N, M)도저히 내가 남에게 설명할 수 있을 만큼은 이해하기가 어렵다.. 어떻게 진행되는지 따라가보면 알긴하겠는데 다시 만들어보라면 그럴 수 없을 것 같다... 그래서 N과 M 12번 문제까지 강행 해볼까 한다.
3번 - 15651
# N과 M (3)
import sys
N, M = map(int, sys.stdin.readline().split())
# visited = [False] * N
out = []
def threeeee(depth, n, m):
if depth == m:
print(*out)
return
for i in range(n):
# if not visited[i]:
out.append(i+1)
threeeee(depth+1, n, m)
# visited[i] = True
out.pop()
# for j in range(i, n):
# visited[j] = False
threeeee(0, N, M)한 수열에 같은 수가 나와도 되며 수열은 사전순으로 증가한다.
처음엔 어리둥절 해서visited를 만들어 해보려 했지만 방문을 체크하는visited가 전혀 필요없는 문제 였다. 가지치기를 할 필요없이DFS로 구하는 문제
4번 - 15652
# N과 M (4)
import sys
N, M = map(int, sys.stdin.readline().split())
visited = [False] * N
out = []
def four(depth, n, m):
if depth == M:
print(*out)
return
for i in range(n):
if not visited[i]:
out.append(i+1)
four(depth+1, n, m)
out.pop()
visited[i] = True
for j in range(i+1, n):
visited[j] = False
four(0, N, M)import sys
N, M = map(int, sys.stdin.readline().split())
out = []
def four(depth, idx, n, m):
if depth == m:
print(*out)
return
for i in range(idx, n):
out.append(i+1)
four(depth+1, i, n, m)
out.pop()
four(0, 0, N, M)
3 3을 입력했는데1 1 1,1 1 2,1 1 3?? 그렇다면visited에True를 앞에서 주면 안되겠네,, 같은 수를 여러번 골라도 되면서 수열이 중복되면 안되는 구나, 그렇다면 다시for문을 돌리면 되려나? 성공!!라는 생각으로 풀었다. 그리고 머지않아 아래의 풀이법을 찾았고 의욕이 급히 하강했다. 너무 하기 싫고 화난다 증말로
5번 - 15654
마음을 가다듬고 5번으로,,
# N과 M (5)
import sys
N, M = map(int, sys.stdin.readline().split())
lst = list(map(int, sys.stdin.readline().split()))
lst.sort()
visited = [False] * N
out = []
# lst = [1, 7, 8, 9]
def five(depth, n, m):
if depth == m:
print(*out)
return
for i in range(n):
if not visited[i]:
visited[i] = True
out.append(lst[i])
five(depth+1, n, m)
out.pop()
visited[i] = False
five(0, N, M)감이 잡혔다. 재귀함수의 형태에서 다음 다음 차원에서
visited의 값을 어떻게 컨트롤해줘야 하는지에 대한 고민을 거듭하고이경원님과 두뇌 풀가동을 해서 우동사리 듀얼코어로 가지치기의 위치를 고민했다. 겨우 겨우 되는가 싶더니 입력값9 8 7 1의 상황에서7 7처럼 중복되는 값이 출력되자 둘다 풀이 꺾여 버렸다.. 해답을 보고는 더 허망했다.6번은 절.대.안.해.
6번 - 15655
# 특이사항이 없어서 앞부분 생략
def six(depth, n, m):
if depth == m:
print(*out)
return
for i in range(n):
if not visited[i]:
out.append(lst[i])
visited[i] = True
six(depth+1, n, m)
out.pop()
for j in range(i+1, n):
visited[j] = False
six(0, N, M)2번 문제와 같은 방식의 문제. 다른 점이 있다면 수열의 값을 입력값으로 정해준다. 손쉽게 풀었다. 풀었다기 보다는 봤던 문제 코드 복붙 수준이긴함,,,
7번 - 15656
def seven(depth, n, m):
if depth == m:
print(*out)
return
for i in range(n):
if not visited[i]:
out.append(lst[i])
seven(depth+1, n, m)
out.pop()
seven(0, N, M)3번처럼 모든 경우의 수를 다 구하는 문제. 같은 수가 여러번 나와도 된다.
8번 - 15657
# 역시나 앞엔 생략
def eight(depth, n, m):
if depth == m:
print(*out)
return
for i in range(n):
if not visited[i]:
out.append(lst[i])
eight(depth+1, n, m)
out.pop()
visited[i] = True
for j in range(i+1, n):
visited[j] = False
eight(0, N, M)4번 문제와 같은 유형. 4번 처럼 간단한 식을 이용해 작성했으나 런타임에러가 나와서 다시 기본식으로 작성했다. 대~애충은 감이 잡힌다. 아쉬운건 뒤로 갈수록 문제가 특별하게 꼬는 것은 없고 살짝만 바뀌어 나온다는 점.
9번 - 15663
def nine(depth, n, m):
if depth == m:
print(*out)
return
check = 0
for i in range(n):
if not visited[i] and check != lst[i]:
out.append(lst[i])
visited[i] = True
check = lst[i]
nine(depth+1, n, m)
out.pop()
visited[i] = False
nine(0, N, M)입력값에 중복되는 수를 입력할 수 있다는 조건이 추가된 5번의 변형이라고 볼 수 있겠다. 다양한 방법을 시도해 봤는데 이게 제일 빠르고 간단한 해법인 것 같다.
10번 - 15664
def ten(depth, idx, n, m):
if depth == m:
print(*out)
return
check = 0
for i in range(idx, n):
if not visited[i] and check != lst[i]:
out.append(lst[i])
visited[i] = True
check = lst[i]
ten(depth+1, i+1, n, m)
out.pop()
visited[i] = False
ten(0,0, N, M)9번의 비내림차순 변형 문제다.
visited에 조건을 주는 방식으로 해결했는데, 문제에 나온 케이스는 전부 통과가 되었지만 백준에서 오답이라고 나왔다. 결국 스스로 해결을 포기하고 답을 찾게되었는데 문제는 정답 코드도 이해가 되지 않는 다는 것. 아니, 이해가 안된다기 보다는 어떻게 이런식을 만들어 냈는지...
비내림차순에 순열의 수의 중복을 허용하지 않는 문제
11번 - 15665
def eleven(depth, n, m):
if depth == m:
print(*out)
return
check = 0
for i in range(n):
if check != lst[i]:
out.append(lst[i])
check = lst[i]
eleven(depth+1, n, m)
out.pop()
eleven(0, N, M)금새 또 적응이 되는지 곧 잘 풀었다. 익숙해지기만 하는 듯.
입력값이 중복되고 출력값은 수열에 같은 수가 여러번 등장해도 되지만 중복되는 수열이 여러 번 출력되면 안되는 문제. 모든 경우의 수를 탐색하지만 중복을 막는 방법을 사용했다.
12번 - 15666
def twelve(depth, idx, n, m):
if depth == m:
print(*out)
return
check = 0
for i in range(idx, n):
if not visited[i] and check != lst[i]:
out.append(lst[i])
check = lst[i]
twelve(depth+1, i, n, m)
out.pop()
twelve(0, 0, N, M)10번 문제에 순열의 숫자 중복을 허용한 문제. 큰 문제없이 풀었지만 아직 완전히 이해 하지 못했다는 생각이 든다.
전부 어떻게든 풀어내긴 했지만, 문제마다 주먹구구식으로 답을 찾았다. 전체적으로 일관성이 없는 풀이, 기억에 맞춰서 기억을 복붙하는 형식의 풀이를 한 것 같다.
