내용으로 건너뛰기
테페리넷
사용자 도구
등록
로그인
사이트 도구
검색
도구
문서 보기
Fold/unfold all
역링크
미디어 관리자
사이트맵
등록
로그인
>
미디어 관리자
사이트맵
현재 위치:
테페리넷
»
Problem Solving
»
문제
»
프로그래머스
»
여행경로
ps:problems:programmers:43164
이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.
====== 여행경로 ====== ===== 풀이 ===== * 모든 엣지를 포함하는 경로, 즉 [[https://en.wikipedia.org/wiki/Eulerian_path|오일러 패스]]를 찾으라는 문제이다. 그냥 흔히 알려진 DFS기반의 알고리즘을 사용하면 된다. * 그래프를 인접 리스트로 표현하고, 각 리스트의 마지막에 있는 에지부터 방문하면서 엣지를 리스트에서 pop()하는 식으로 구현하였다. 즉, 리스트의 끝에 있는 엣지부터 사용하게 되므로, 알파벳 순으로 탐색하기 위해 리스트를 알파벳의 역순으로 정렬하였다 * 시간복잡도는 소팅에 O(ElogE) + 탐색에 O(E)인데, 문제에서 V≤10000 이라고만 주어지고, E에 대해서는 범위가 주어지지 않는다. 심플 그래프라는 보장이 없어서 E<V^2 인것도 보장이 안된다. 만약에 중복 엣지가 매우 많아서 E>>V^2 라면, 그래프에 모든 엣지를 리스트에 넣는 것이 아니라, 중복 엣지를 묶어서 (엣지, 개수) 식으로 저장한다면 소팅 단계를 O(V^2logV)로 줄일수는 있을 것이다 (구현은 안함). ===== 코드 ===== <dkpr py> """Solution code for "Programmers 43164. 여행경로". - Problem link: https://programmers.co.kr/learn/courses/30/lessons/43164 - Solution link: http://www.teferi.net/ps/problems/programmers/43164 """ import collections def dfs_rec(graph, u): ret = [] while graph[u]: ret = dfs_rec(graph, graph[u].pop()) + ret return [u] + ret def solution(tickets): graph = collections.defaultdict(list) for u, v in tickets: graph[u].append(v) for nodes in graph.values(): nodes.sort(reverse=True) return dfs_rec(graph, 'ICN') </dkpr> {{tag>프로그래머스 ps:problems:programmers:Level_3}}
ps/problems/programmers/43164.txt
· 마지막으로 수정됨: 2021/06/30 08:22 저자
teferi
문서 도구
문서 보기
역링크
Fold/unfold all
맨 위로