주제 - “알고리즘 (DFS/BFS) - 4”
부제 - 프로그래머스 코딩테스트 연습 - 파이썬
출처 - 프로그래머스 - 코딩테스트 연습 - 해시 - 여행경로
- 문제의 풀이는 다른 사람의 풀이 중 공부하고 싶은 것을 스크랩한 것입니다.
문제 4. 여행경로
[문제 설명]
주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다. 항상 ICN 공항에서 출발합니다.
항공권 정보가 담긴 2차원 배열 tickets가 매개변수로 주어질 때, 방문하는 공항 경로를 배열에 담아 return 하도록 solution 함수를 작성해주세요.
[제한사항]
- 모든 공항은 알파벳 대문자 3글자로 이루어집니다.
- 주어진 공항 수는 3개 이상 10,000개 이하입니다.
- tickets의 각 행 [a, b]는 a 공항에서 b 공항으로 가는 항공권이 있다는 의미입니다.
- 주어진 항공권은 모두 사용해야 합니다.
- 만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 합니다.
- 모든 도시를 방문할 수 없는 경우는 주어지지 않습니다.
[입출력 예]
| tickets | return |
|---|---|
| [[“ICN”, “JFK”], [“HND”, “IAD”], [“JFK”, “HND”]] | [“ICN”, “JFK”, “HND”, “IAD”] |
| [[“ICN”, “SFO”], [“ICN”, “ATL”], [“SFO”, “ATL”], [“ATL”, “ICN”], [“ATL”,”SFO”]] | [“ICN”, “ATL”, “ICN”, “SFO”, “ATL”, “SFO”] |
풀이
def solution(tickets):
x = len(tickets) + 1
answer = ["ICN"]
stack = ["ICN"]
while len(answer) != x:
bfs = stack.pop()
for a, b in tickets:
if a == bfs:
stack.append(b)
stack.sort()
answer.append(stack[0])
tickets.pop(tickets.index([bfs, stack[0]]))
stack = [answer[-1]]
return answer
def solution(tickets):
def dfs(tickets, route):
if tickets == []:
return route
# route를 최종 리턴
left = [i for i in range(len(tickets)) if tickets[i][0] == route[-1]]
if left == []:
return None
left.sort(key = lambda i: tickets[i][1])
for next in left:
rest = dfs(tickets[:next]+tickets[next+1:], route+[tickets[next][1]])
#rest는 dfs의 리턴값
if rest is not None:
return rest
# dfs의 리턴값을 최종 리턴
return dfs(tickets, ["ICN"])
def solution(tickets):
def dfs(tickets, route):
if tickets == []: return route
stack = [b for a,b in tickets if a == route[-1]]
if stack == []: return None
stack.sort()
for i in stack:
tickets.pop(tickets.index([route[-1], stack[0]]))
route.append(stack.pop(0))
next = dfs(tickets, route)
if next is not None: return next
return dfs(tickets, ["ICN"])
풀이의 포인트
시작 단어에서 알파벳 하나씩만을 바꿔가며 words에 있는 단어로 바꾼 후, 최종적으로 목표 단어를 만드는 문제입니다.
목표 단어를 만들기 위해서는 시작 단어에서 하나만 다른 단어가 words에 존재해야 합니다. 그리고 그렇게 하나씩 다른 단어를 찾아가야 합니다.
1) 문제 파악하기 : BFS
알파벳 하나씩만을 바꿔가며 단어를 만들기 위해, words에서 시작단어와 한글자만 다른 단어를 찾아야 합니다.
words에서 그런 단어를 찾기 위해서는 시작 단어와 하나씩 비교를 해봐야 합니다. 그렇게 원하는 단어를 찾았다면, 또 그 다음 단어를 찾기 위해 words의 단어와 하나씩 비교를 해야합니다.
그렇게 words의 단어를 여러차례 순회하기 위해 BFS를 이용합니다.
2) 단어 비교 함수 작성
먼저, 시작 단어인 begin으로부터 알파벳이 하나만 다른 단어를 words에서 찾아야합니다. 물론 이후에도 계속해서 알파벳이 하나만 다른 단어를 찾아야 합니다.
그를 위해 알파벳이 하나만 다른 단어를 찾기 위한 함수를 먼저 작성합니다.
비교 대상은 한 단어와 words에서 뽑아낸 단어, 알파벳 하나하나를 비교합니다. 알파벳 하나하나를 비교하기 위해 단어 두개를 zip으로 묶습니다.
>>> a = "hit"
>>> b = "hot"
>>> cmp = zip(a, b)
>>> next(cmp)
('h', 'h')
>>> next(cmp)
('i', 'o')
>>> next(cmp)
('t', 't')
그렇게 zip으로 묶은 단어는 아래와 같이 반복문을 사용하여 알파벳 하나하나를 비교할 수 있습니다.
>>> a = "hit"
>>> b = "hot"
>>> cmp = zip(a, b)
>>> for x,y in zip(a,b):
if x != y:
print("다르다")
else:
print("같다")
같다 # ('h', 'h')
다르다 # ('i', 'o')
같다 # ('t', 't')
단어를 비교하는 이유는 알파벳이 하나만 다른 단어를 찾기 위함입니다. 그를 위해 단어를 비교하고 알파벳이 다른 개수를 체크합니다.
알파벳이 같으면 0, 다르면 1로 체크하여 단어를 전부 비교한 뒤 합을 냅니다. 그렇게 합이 1이 되는 단어가 알파벳이 하나만 다른 단어가 되는 것입니다. 이를 함수로 만들면 아래와 같습니다.
이 함수는 알파벳이 하나만 다른 단어에 대해 True를 리턴합니다.
>>> transistable = lambda a, b: sum((1 if x!=y else 0) for x,y in zip(a,b)) == 1
3) collections 모듈의 deque : deque 형태의 object를 리턴하는 클래스
deque(double-ended queue) : 양방향에서 데이터를 처리할 수 있는 queue
[지원하는 메소드]
- append(x) : deque의 우측에 x 추가
- appendleft(x) : deque의 좌측에 x 추가
- insert(i, x) : deque의 i번째 위치에 x 추가
- clear : deque의 모든 요소 삭제
- pop() : deque의 우측에서 값 하나 추출
- popleft() : deque의 좌측에서 값 하나 추출
- remove(value) : deque에서 처음 나타나는 value 삭제
ex)
>>> from collections import deque >>> q = deque() >>> q deque([]) >>> q.append('b') >>> q deque(['b']) >>> q.append('c') >>> q deque(['b', 'c']) >>> q.appendleft('a') >>> q deque(['a', 'b', 'c'])
BFS를 구현하기 위해 큐를 사용합니다. 이번 풀이에서는 큐를 구현하기 위해 deque를 사용합니다.
이 큐는 알파벳 하나씩 바꿔가는 단어를 표시해두기 위해 사용합니다.
>>> from collections import deque as queue
>>> begin = "hit"
>>> q = queue()
>>> q
deque([])
>>> q.append((begin, 0))
>>> q
deque([('hit', 0)])
4) 내장함수 filter : 인자의 iterator를 인자의 함수에 대입하여 값이 True인 요소들로 새로운 iterator을 구성하는 함수
ex)
>>> a = [1, 2, 3, 4, 5] >>> b = filter(lambda x:x%2 == 1, a) >>> b <filter object at 0x034729D0> >>> c = set(filter(lambda x:x%2==1, a)) >>> c {1, 3, 5} >>> d = list(filter(lambda x:x%2==1, a)) >>> d [1, 3, 5]
이 함수는 아까 만들어둔 단어 비교 함수를 사용하기 위해 사용합니다. 단어 비교 함수와 (단어, words)를 인자로 하여 filter를 사용합니다.
아까 만든 단어 비교 함수는 단어 두 개를 비교하여 알파벳이 하나만 차이나는 단어를 찾으면 True를 리턴합니다. 그렇기에 이 함수를 인자로 아래와 같이 filter를 사용하면 알파벳이 하나만 차이나는 단어 set을 얻을 수 있습니다.
>>> begin = "hit"
>>> words = ["hot", "dot", "dog", "lot", "log", "cog"]
>>> d = dict()
>>> d
{}
>>> d[begin] = set(filter(lambda x:transistable(x, begin), words))
>>> d
{'hit': {'hot'}}
그리고 위와 같은 방법을 이용해, words 리스트의 단어도 하나씩 차이나는 단어들을 체크해 둡니다.
>>> words = ["hot", "dot", "dog", "lot", "log", "cog"]
>>> for w in words:
d[w] = set(filter(lambda x:transistable(x, w), words))
>>> d
{'hit': {'hot'}, 'hot': {'dot', 'lot'}, 'dot': {'hot', 'dog', 'lot'}, 'dog': {'dot', 'log', 'cog'}, 'lot': {'hot', 'dot', 'log'}, 'log': {'dog', 'cog', 'lot'}, 'cog': {'dog', 'log'}}
5) 코드 구현하기
알파벳이 하나만 차이나는 단어를 체크한 dictionary 를 만들었다면, 이제 순서를 잘 조합하여 begin에서 target으로 단어를 만들 차례입니다.
위에서 만들어둔 큐를 이용합니다. 큐에 담아둔 단어를 이용하여 본격적으로 단어가 변환하는 과정을 확인합니다.
먼저 큐에서 단어를 뽑고, 단어를 체크한 dictionary에서 해당 단어와 이어질 단어를 체크합니다. 그리고 그 변환 과정의 횟수 또한 함께 체크합니다.
그리고 이 단어와 변환 과정의 횟수는 다시 큐에 삽입됩니다. 목표 단어에 도달하고, 그 단어로 변환하기까지의 횟수를 얻기 위함입니다.
본 코드에서는 단어는 cur, 변환 과정의 횟수를 level에 담아 저장합니다.
>>> q
deque([('hit', 0)])
>>> d
{'hit': {'hot'}, 'hot': {'dot', 'lot'}, 'dot': {'hot', 'dog', 'lot'}, 'dog': {'dot', 'log', 'cog'}, 'lot': {'hot', 'dot', 'log'}, 'log': {'dog', 'cog', 'lot'}, 'cog': {'dog', 'log'}}
>>> cur, level = q.popleft()
>>> cur
'hit'
>>> level
0
>>> for w in d[cur]:
q.append((w, level + 1))
>>> q
deque([('hot', 1)])
여기서 최종적으로 목표 단어를 만들기 위해서는 몇 가지가 더 필요합니다.
먼저 단어를 채운 큐를 목표 단어를 만들 때까지 탐색하기 위해 반복문이 필요합니다. 그리고 목표 단어가 완성되면 변환 횟수를 리턴해야 합니다.
>>> for w in d[cur]:
if w == target:
return level + 1
else:
q.append((w, level + 1))
만약 words를 다 탐색했음에도 목표 단어가 만들어지지 않았다면, 단어를 만들 수 없는 것이므로 0을 리턴해야 합니다.
그리고 큐의 단어를 모두 소비했음에도 목표 단어가 만들어지지 않았다면, 그 또한 단어를 만들 수 없는 것이므로 0을 리턴해야 합니다.
>>> while q:
cur, level = q.popleft()
if level > len(words):
return 0
return 0
따라서 최종적으로 완성되는 코드는 아래와 같습니다.
from collections import deque as queue
transistable = lambda a,b: sum((1 if x!=y else 0) for x,y in zip(a,b)) == 1
def solution(begin,target,words):
q, d = queue(), dict()
q.append((begin, 0))
d[begin] = set(filter(lambda x:transistable(x,begin), words))
for w in words:
d[w] = set(filter(lambda x:transistable(x,w), words))
while q:
cur, level = q.popleft()
if level > len(words):
return 0
for w in d[cur]:
if w == target:
return level + 1
else:
q.append((w, level + 1))
return 0