[Python] 프로그래머스 타겟넘버, 프로그래머스 여행경로

1. 문제: https://school.programmers.co.kr/learn/courses/30/lessons/43165

해당 문제는 DFS로 풀이할 수 있다.

- 더하거나 뺀다 --> 가지치기 -> 트리구조와 유사

- 시작 조건은 0이고, 종료 조건 (target) 존재 --> 종료 조건이 있음. 즉 시작부터 종료 조건까지 탐색하는 그래프 탐색

 

✅ 풀이

answer = 0

def solution(numbers, target):
    
    def dfs(depth, count, index):     
        global answer
        
        if depth == len(numbers) and sum == target:  # n개의 정수로 합계가 target일 경우, count + 1
            answer += 1
            return
        
        if index >= len(numbers):    # 인덱스가 out of range일 경우 return
            return
            
        dfs(depth+1, sum + numbers[index], index+1)
        dfs(depth+1, sum - numbers[index], index+1)
        
    dfs(0, 0, 0)
    
    return answer

 

여기서 추가적으로 궁금해서 찾아본 부분은, 처음 코드를 작성했을 당시의 오류이다.

 

1) local variable 'answer' referenced before assignment

def solution(numbers, target):
    
    answer = 0
    
    def dfs(depth, sum, index):
        
        if depth == len(numbers) and sum == target:
            answer += 1

    # --- 중략 ---
    
    return answer

 

- python은 값을 변경하려고 하는순간, local 변수 취급하기 때문에 dfs 함수 내에서 찾지만 answer 변수가 할당되지 않았기 떄문에 오류 발생

 

2) name 'answer' is not defined

def solution(numbers, target):
    
    answer = 0
    
    def dfs(depth, sum, index):
    	global answer
        
        if depth == len(numbers) and sum == target:
            answer += 1

    # --- 중략 ---
    
    return answer

 

- 위에서 answer를 global로 선언하였지만, 막상 answer가 solution 함수의 내부 로컬 변수이지 전역변수가 아니기 때문에 찾을수가 없음

 

=> 해결 방법은 다음과 같다.

 

1) answer 변수를 solution 함수 안에서 선언하되, dfs 중첩 함수에서 nonlocal 선언

def solution(numbers, target):
    
    answer = 0
    
    def dfs(depth, sum, index):
        nonlocal answer

 

2) answer 변수를 solution 함수 밖에서 선언하되, dfs 중첩 함수에서 global 선언

answer = 0

def solution(numbers, target):
        
    def dfs(depth, sum, index):
        global answer

 

2. 문제: https://school.programmers.co.kr/learn/courses/30/lessons/43164

문제 요약

- 주어진 항공권은 모두 사용해야함

- 항공권은 모든 도시를 방문할 수 있는 경우만 주어짐

- 가능한 경로가 2개 이상일 경우, 알파벳 순서가 앞서는 경로를 answer로 선택

 

✅ 풀이

def solution(tickets):
    answer = []
    visited = [False] * len(tickets)    # 1.
    
    def dfs(start, path): 
        if len(path) == len(tickets) + 1:    # 2.
            answer.append(path)
            return
        
        for idx, ticket in enumerate(tickets):
            if not visited[idx] and ticket[0] == start:   # 3.
                visited[idx] = True   # 4.
                dfs(ticket[1], path + [ticket[1]])   # 5.
                visited[idx] = False   # 6.
                
    dfs("ICN", ["ICN"])

    answer.sort()    # 7.
    
    return answer[0]

 

- DFS + 백트래킹을 활용하여 풀이하는 풀이이다. 백트래킹이란, 탐색하다가 가능성이 없는 곳에서 돌아가 다시 가능성이 있는곳으로 탐색하는 기법이다.

- 문제 조건에 "주어진 항공권은 모두 사용해야한다", "가능한 경로가 2개 이상일 수 있다 --> 가지치기" 라는 내용에서 조건이 맞지 않으면 돌아가 다시 가능한 티켓을 탐색해야함을 알수있다. (백트래킹)

 

1. 방문하는 공항 경로의 모든 조합을 구하기 위한 티켓 사용여부를 저장할 배열을 만든다.

(우선 방문처리 한다음에 해당 공항 경로를 알아보다가, 조건이 맞지않으면 돌아가서 다시 탐색해야므로 탐색할 경로 후보를 복원하기 위함) 

2. 경로의 길이와 티켓의 길이 + 1이라는 것은 ICN 포함한 모든 티켓을 사용하여 모든 도시를 방문했다는 의미이므로, 이 조건에 맞을 시 정답이 될 수 있는 후보지인 answer 배열에 저장 후, 다른 후보를 탐색하기 위해 되돌아간다. (return)

3. not visited: 후보지중, ticket[0] == start: 현재 도시에서 티켓을 사용하여 갈 수 있는 경로라면

4. 티켓을 사용처리하여

5. 그 다음 후보지를 탐색한 다음,

6. 다른 티켓을 사용했을 때를 판단하는 경우를 판단하기 위해 티켓 사용여부를 복원처리한다.

(예: 예를들어 ["ICN, "SFO"] 와 ["ICN", "ATL"] 이 있을 때 2가지 티켓이 존재하므로, 전자를 먼저 사용했을 때의 경로와 후자를 먼저 사용했을때의 경로를 모두 따져볼 수 있으므로 방문 여부를 복원처리 해야함)

7. 문제 조건에 "가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 한다" 라고 나와있어, 알파벳 순으로 정렬한 후 제일 앞서는 경로를 return한다.

 

오늘의 배운점

- Python에서, 함수 내 변수를 변경하고자 할 때 함수는 해당 변수를 local 변수로 취급한다. 따라서 해당 변수를 전역 변수로 빼거나 nonlocal 처리하자

- 명확한 종료 조건 혹은 해가 있고, 탐색 시 가지치기할 수 있는 조건이 있을 때 백트래킹을 고려하자.