[프로그래머스] 여행경로 (level3, python)

 

 

🤔 풀이 코드

 

from collections import deque
import copy

def bfs(start, ways, visited, n):
    queue = deque()
    queue.append([start, start, visited])
    candidate = []
    
    while queue:
        now, log, visit = queue.popleft()
        if len(log) == 4 * n - 1:
            candidate.append(log)
            continue
        for next in ways[now]:
            visited_key = now + next
            if visit[visited_key] != 0:
                visit[visited_key] -= 1
                queue.append([next, log + " " + next, copy.deepcopy(visit)])
                visit[visited_key] += 1
        
    return sorted(candidate, key = lambda x : x)[0].split(" ")
    
def solution(tickets):
    ways = {}
    visited = {}
    
    for way in tickets:
        start, end = way
        visited_key = start + end
        if visited_key in visited:
            visited[visited_key] += 1
        else:
            visited[visited_key] = 1
            
        if start not in ways:
            ways[start] = [end]
        else:
            ways[start].append(end)
        
        if end not in ways:
            ways[end] = []
    
    return bfs("ICN", ways, visited, len(tickets)+1)

 

 

🤔 문제 풀이

 

쉬운 문제인줄 알았으나, 고려해야 할 요소가 생각보다 많아서 애를 먹었던 문제입니다.

다음은 놓치기 쉬운 조건입니다.

- 같은 A -> B행 티켓이 여러 장인 경우가 있을 수 있다. 문제의 조건 어디에도 이러한 경우가 없다는 제한이 없다.

- visited 처리를 할 때, 각 노드를 방문한 여부를 체크하는 것이 아니라, 해당 티켓을 소비했느냐?의 관점으로 체크해야 함. 같은 장소를 여러번 방문할 수 있기 때문.

 

저는 BFS를 활용해서 문제를 풀이했습니다.

방문 장소가 아닌, 티켓을 기준으로 visited를 만들기 위해, visited_key를 만들어서 관리했습니다.

ex) "AAA" -> "BBB"라면, visited의 key는 "AAABBB"

 

그 후, ticket의 개수 + 1개의 노드가 로그에 찍히고, 각 노드는 길이가 3인 문자열이기 때문에 모든 티켓을 소모한 후 로그의 총 길이(공백 포함)는, 4n - 1이 됩니다. 이러한 조건을 적용해 정답 후보군 리스트에 삽입합니다.

 

visit 딕셔너리와 deepcopy를 활용해서, 각 여행 루트마다 방문 여부를 다르게 관리하도록 했습니다.

for문의 특성상 append 앞과 뒤에 방문 처리 여부 조정을 위해 1을 빼주고, 더해주는 연산을 삽입했습니다.

뒤에서 더해주지 않으면 다음 for문 실행에 영향이 가기 때문입니다.

 

최종적으로 완성된 로그의 후보들을 sorting한 다음, 가장 첫 원소를 공백을 기준으로 split을 한다면 정답이 됩니다.