-
[탐색] 여행 경로 (python)코딩 테스트/프로그래머스 2023. 4. 16. 20:05
문제 설명
https://school.programmers.co.kr/learn/courses/30/lessons/43164
문제 풀이
- BFS/DFS 중에서 BFS로 접근
- 경로가 여러개 일 경우 알파벳 순으로 사용하므로 ticket들 정렬
- gr이라는 딕셔너리에 [출발 지역]:[tickets idx] 저장
- 큐에 현재 공항, 이용한 경로, 사용한 티켓 idx 를 담음
- 이용 경로의 갯수와 티켓+1 이 같으면 종료 (모두 사용한 거니까)
- 딕셔너리에서 키 값이 없는 것을 그냥 꺼내오면 에러가 나서 get으로 걸러내기
- 이 후에는 기본 bfs
소스 코드
from collections import deque def solution(tickets): answer = [] tickets.sort() n = len(tickets) gr = dict() #[출발점]:[출발점의 tickets idx] for i in range(n): s,e=tickets[i] if not gr.get(s): gr[s]=[] gr[s].append(i) q = deque() q.append(("ICN",["ICN"],[])) #현재 공항, answer가 될 path, 사용한 티켓 idx 저장 while(q): cur, path, ticekt = q.popleft() if(len(path)==(n+1)): # 사용 티켓 수 answer=path break if not gr.get(cur): # INC,BOO ICN,COO, COO,ICN 같은 경우 막기 위한 조건(ICN-BOO부터 사용하면 에러남) continue for t in gr[cur]: if t in ticekt: continue end = tickets[t][1] q.append((end,path+[end],ticekt+[t])) return answer print(solution([["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "SFO"], ["ATL","ICN"]]))
'코딩 테스트 > 프로그래머스' 카테고리의 다른 글
[파이썬] 기지국 설치 (0) 2023.04.17 [2021 카카오 블라인드] 합승 택시 요금 (파이썬) (0) 2023.04.17 [그리드] 섬 연결하기 (python) (1) 2023.04.11 [그래프] 가장 먼 노드 (0) 2023.04.10 [2020 카카오 인턴십] 스티커 모으기(2) (0) 2023.04.07