[13일차] TIL - Back Tracking

알고리즘 주제 - 백트래킹

백트래킹에 대해 공부하고 leetcode 51번 문제를 예제로 풀어보고 다음 3문제를 풀었습니다.

 

백트래킹이란

현재 상태에서 가능한 모든 경로를 따라 들어가 탐색하다, 원하는 값과 불일치하는 부분이 발생하면 더 이상 탐색을 진행하지 않고 전단계로 되돌아갑니다. (back-tracking)

 

백트래킹과 DFS를 혼동하기 쉬운데 엄밀히 말하면 서로 다른 개념이라고 할 수 있습니다.

 

백트래킹은 원하는 값과 경로가 다르면 더 이상 해당 경로는 탐색하지 않지만 DFS는 원하는 경우가 아니더라도 모든 경우의 수를 탐색합니다.

 

1. N - Queen

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

 

다음과 같이 풀었지만 30초가 넘는 시간이 나오면서 어쩔 땐 정답판정을 받았지만 어쩔 땐 시간 초과가 뜨기도 하였습니다.

n = int(input())

visited = [-1] * n
cnt = 0

def is_ok_on(nth_row):
    for row in range(nth_row):
        if visited[row] == visited[nth_row] or nth_row - row == abs(visited[nth_row] - visited[row]):
            return False
    return True

def dfs(row):
    global cnt
    if row >= n:
        cnt += 1
        return

    for col in range(n):
        visited[row] = col
        if is_ok_on(row):
            dfs(row + 1)

dfs(0)
print(cnt)

최적화된 풀이를 구글링으로 찾았지만 이 마저도 10초가 넘는 시간이 걸렸습니다. 제 예상으로는 파이썬의 연산 속도가 늦어서 생기는 문제가 아닌가 싶습니다. 참고로 C언어는 1초에 1억번 파이썬은 1초에 백만번의 연산을 할 수 있다고 알고 있습니다.

 

 

2. 1, 2, 3 더하기

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

 

t = int(input())
result = []

def dfs(num, sum):  # (4, 0)
    global count
    # 더한 값이 구하는 값보다 크다면 return
    if num < sum:
        return

    # 더한 값이 구한 값과 같다면 개수 추가
    if num == sum:
        count += 1
        return

    for i in range(1, 4): # 1, 2, 3 # i = 1
        sum += i                    # sum = 1
        # dfs 재귀적 수행
        dfs(num, sum)           # dfs(4, 1)
        sum -= i


# 입력받고 dfs 메서드 수행
for _ in range(t):
    num = int(input()) # 4
    count = 0
    dfs(num, 0)
    result.append(count)

# 결과 출력
for answer in result:
    print(answer)

 

 

 

3. 암호 만들기

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

 

처음 다음과 같이 DFS로 풀었습니다. 

l, c = map(int, input().split()) # 4 6
letters = list(input().split())
vowels = ['a', 'e', 'o', 'i', 'u']
result = []
vo_cnt = 0
not_vo = 0
def dfs(index, path): # (0, '')
    if len(path) == l:
        vo_cnt = 0
        not_vo = 0
        path = sorted(path)
        for each in path:
            if each in vowels:
                vo_cnt += 1
            else:
                not_vo += 1

            if path not in result and vo_cnt > 0 and not_vo > 1:
                result.append(path)
        return

    for i in range(index, c): # i=0 index=0 c=6
        for j in letters[i]:     # 'a'
            dfs(i + 1, path + j) # (1, 'a')


dfs(0, '')


for i in range(len(result)):
    result[i] = ''.join(result[i])

result.sort()
for answer in result:
    print(answer)

 

좀 더 나은 방법으로 풀어보고자 combinations를 이용하였는데, 출력초과가 나왔습니다. 해답은 아직 찾고 있는 중 입니다.

letters = list(input().split())
vowels = ['a', 'e', 'i', 'u', 'o']
vo_cnt = 0

from itertools import combinations

result = []
answer = []

word_list = list(combinations(letters, 4))
for word in word_list:
    result.append(''.join(sorted(word)))

for word in result:
    vo_cnt = 0
    for each in word:
        if each in vowels:
            vo_cnt += 1

    if vo_cnt > 0 and vo_cnt < l - 1 and word not in answer: # l - 1
        answer.append(word)

answer.sort()
for ans in answer:
    print(ans)