[ 파이썬 ] 파이썬 Dictionary를 이용해 그래프 만들기 / defaultdict() 활용하기 ( from collections import defaultdict )

DFS나 BFS를 풀 때 그래프를 만들어 풀면 수월한 문제들이 있다

예를 들어 ( 프로그래머스 여행경로 문제  )

코딩테스트 연습 - 여행경로

• 항공권 정보가 담긴 2차원 배열 tickets가 매개변수로 주어질 때
• tickets의 각 행 [a, b]는 a 공항에서 b 공항으로 가는 항공권이 있다는 의미이다

[["ICN", "SFO"], 
["ICN", "ATL"], 
["SFO", "ATL"], 
["ATL", "ICN"], 
["ATL","SFO"]]

 

이를 딕셔너리를 사용하여 그래프를 만들면

• 첫 번째 방법

routes = {}
for key, value in tickets:
	if key in routes:
		routes[key].append(value)
	else:
		routes[key] = [value]

>>> {'ICN': ['SFO', 'ATL'], 'SFO': ['ATL'], 'ATL': ['ICN', 'SFO']}

 

• defaultdict()를 활용한 이보다 간편한 두 번째 방법 -> 키가 있는지 확인할 필요가 없다

from collections import defaultdict

routes = defaultdict(list)
for key, value in tickets:
	routes[key].append(value)
   
>>> defaultdict(<class 'list'>, {'ICN': ['SFO', 'ATL'], 'SFO': ['ATL'], 'ATL': ['ICN', 'SFO']})

 

 

+ defaultdict() 활용법

• defaultdict()는 인자로 주어진 객체의 기본값을 딕셔너리 값의 초기값으로 지정할 수 있다.
• 숫자, 리스트, 셋 등으로 초기화 할 수 있다.
• 외부 함수이기 때문에 import 해야 됨 -> from collections import defaultdict

1. 숫자로 초기화 -> 값을 지정하지 않으면 0으로 초기화 ex) 알파벳 횟수 계산
2. 리스트로 초기화 -> 값을 지정하지 않으면 빈 리스트로 초기화 ex) 그래프 경로, 같은 성을 가진 이름끼리 취합하기 
3. 셋으로 초기화 -> 값을 지정하지 않으면 빈 리스트로 초기화

# 1번 숫자로 초기화

from collections import defaultdict
int_dict = defaultdict(int)
int_dict
>>> defaultdict(<class 'int'>, {}) # 디폴트값이 int인 딕셔너리

# 값 지정 안하면 0으로 초기화
int_dict['key1']
>>> 0
int_dict
>>> defaultdict(<class 'int'>, {'key1': 0}) 

# 값 지정하면 그 값으로 지정
int_dict['key2'] = 'test'
int_dict
>>> defaultdict(<class 'int'>, {'key1': 0, 'key2': 'test'}) 

# 리스트로 초기화

from collections import defaultdict
list_dict = defaultdict(list)
list_dict
>>> defaultdict(<class 'list'>, {}) # 디폴트값이 list인 딕셔너리

list_dict['key1'] # 값을 지정하지 않으면 빈 리스트로 초기화
>>> []

list_dict['key2'] = 'test' # 값을 지정하면 해당값으로 초기화
list_dict
>>> defaultdict(<class 'list'>, {'key1': [], 'key2': 'test'}) 

( 참고 : 유사 딕셔너리 defaultdict() 활용법 )