Level 3
문제
정답(1) - BFS
from collections import deque
def solution(tickets):
answer = []
q = deque()
q.append(("ICN",["ICN"], []))
while q:
start, path, used = q.popleft()
if len(used) == len(tickets):
answer.append(path)
for i in range(len(tickets)):
for j in range(len(tickets[i])):
if tickets[i][0] == start and not i in used:
q.append((tickets[i][1], path+[tickets[i][1]], used+[i]))
# for idx, ticket in enumerate(tickets):
# if ticket[0] == airport and not idx in used:
# q.append((ticket[1], path+[ticket[1]], used+[idx]))
answer.sort()
return answer[0]정답(1) - DFS
def solution(tickets):
answer = []
visited = [0]*len(tickets)
def dfs(start, path):
if len(path) == len(tickets)+1:
answer.append(path)
return
for i in range(len(tickets)):
for j in range(len(tickets[i])):
# print(i, tickets[i])
if start == tickets[i][0] and visited[i] == 0:
visited[i] = 1
dfs(tickets[i][1], path+[tickets[i][1]])
visited[i] = 0
# for idx, ticket in enumerate(tickets):
# print(idx, ticket)
# if airport == ticket[0] and visited[idx] == False:
# visited[idx] = True
# dfs(ticket[1], path+[ticket[1]])
# visited[idx] = False
dfs("ICN", ["ICN"])
answer.sort()
return answer[0]정답(2) - DFS
from collections import defaultdict
def solution(tickets):
# 특정 티켓의 인접 리스트를 구하는 함수
def init_graph():
routes=defaultdict(list) #디폴트 값이 리스트인 딕셔너리
for key, value in tickets:
# print(key, value)
routes[key].append(value)
return routes
# 재귀 호출을 사용한 DFS
def dfs(key, footprint):
if len(footprint) == n+1:
return footprint
print(routes[key])
for idx, val in enumerate(routes[key]):
print(idx, val)
routes[key].pop(idx) #이용한 공항은 제거
fp=footprint[:] #리스트 전체를 복사함
fp.append(val) #이용한 공항 루트 넣어줌
ret= dfs(val, fp)
if ret :
return ret #모든 티켓을 사용해 통과한 경우
print(idx, val)
routes[key].insert(idx, val)
routes=init_graph()
for i in routes:
routes[i].sort()
n=len(tickets)
answer = dfs("ICN", ["ICN"])
return answer정답(3) - DFS
DFS를 이용해 모든 티켓을 사용하는 경로를 탐색합니다. 이때 DFS의 순서를 스택에 저장했다가 스택 top에서 갈 수 있는 경로가 없을 경우에 answer에 추가합니다. 갈 수 있는 경로가 없다는 것은 그 공항이 제일 마지막 방문지라는 의미입니다. 즉, answer에는 공항을 방문하는 순서가 거꾸로 저장되게 됩니다. 따라서 마지막에 answer을 뒤집어서 반환하면 됩니다.
- { 시작점: [도착점들] } 의 형태로 그래프 생성
- 도착점들의 리스트를 역순 정렬
(1) 알파벳 순서상 빠른 것이 우선시되기 때문!
(2) 역순으로 정렬해줌으로써 백트래킹처럼 모든 방법을 탐색하지 않고도 원하는 답을 한번에 찾을 수 있다!- 출발점은 항상 "ICN"이므로 스택에 먼저 넣어두기
- DFS를 통해서 모든 노드를 순회 (스택이 빌 때까지 아래를 반복)
4-1. 스택에서 가장 위에 저장된 데이터 top 꺼내오기
4-2. 만약 top이 그래프에 없거나, top을 시작점으로 하는 티켓이 없는 경우 path에 저장
4-3. 2번이 아니라면, top을 시작점으로 하는 도착점 리스트에서 pop 해와 스택에 저장
5.path에 저장된 값들을 거꾸로 뒤집어서 return
from collections import defaultdict
def solution(tickets):
path = []
# 1. {시작점: [도착점리스트]} 형태로 그래프 생성
graph = defaultdict(list)
for (start, end) in tickets:
graph[start].append(end)
# 2. 도착점 리스트를 역순 정렬
for airport in graph.keys():
graph[airport].sort(reverse=True)
# 3. 출발지는 항상 ICN이므로 stack에 먼저 넣어두기
stack = ["ICN"]
# 4. DFS로 모든 노드 순회
while stack:
# 4-1. 스택에서 가장 위의 저장된 데이터 꺼내오기
top = stack.pop()
# 4-2. top이 그래프에 없거나, top을 시작점으로 하는 티켓이 없는 경우 path에 저장
if top not in graph or not graph[top]:
path.append(top)
# 4-3. top을 다시 스택에 넣고 top의 도착점 중 가장 마지막 지점을 꺼내와 스택에 저장
else:
stack.append(top)
stack.append(graph[top].pop())
# 5. path를 뒤집어서 반환
return path[::-1]# 처음부터 끝까지 -1칸 간격으로 ( == 역순으로)코드 과정 자세한 설명
시행 착오
DFS - 틀린 답
처음에 내가 작성한 코드는 아래와 같다. 하지만 테스트 1, 2를 통과하지 못했다.. DFS 말고, BFS로도 풀어봤다.
프로그래머스 -힌트
힌트를 보고해도 안풀렸다..ㅠㅠ 그래서 여러 사람들의 코드를 참고해서 학습하며 해결했다..
from collections import deque
def solution(tickets):
tickets.sort()
m=len(tickets)
visited=[0] * m
def dfs(s):
q=deque()
q.append(s)
while q:
a=q.popleft()
# print(answer)
for i in range(len(tickets)):
for j in range(len(tickets[i])):
if(tickets[i][0]==a and visited[i]==0):
answer.append(tickets[i][1])
visited[i]=1
dfs(tickets[i][1])
break
return answer
answer = ["ICN"]
res=dfs("ICN")
return res
BFS - 틀린 답
from collections import deque
def solution(tickets):
tickets.sort()
m=len(tickets)
visited=[0] * m
def dfs(s):
q=deque()
q.append(s)
while q:
a=q.popleft()
answer.append(a)
for i in range(len(tickets)):
for j in range(len(tickets[i])):
if(tickets[i][0]==a and visited[i]==0):
visited[i]=1
q.append(tickets[i][1])
a=""
return answer
answer = []
res=dfs("ICN")
return res
I believe in myself.