반응형
https://www.acmicpc.net/problem/2644
2644번: 촌수계산
사람들은 1, 2, 3, …, n (1≤n≤100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어진�
www.acmicpc.net

BFS 문제.
2d array 대신 dictionary를 이용했다.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import sys | |
from collections import defaultdict, deque | |
n = int(sys.stdin.readline()) | |
a, b = map(int, sys.stdin.readline().split()) | |
m = int(sys.stdin.readline()) | |
connected = defaultdict(set) | |
for _ in range(m): | |
parent, child = map(int, sys.stdin.readline().split()) | |
connected[parent].add(child) | |
connected[child].add(parent) | |
def bfs(start, connected, end): | |
visited = set() | |
queue = deque() | |
queue.append((0, start)) | |
while queue: | |
cnt, p = queue.popleft() | |
visited.add(p) | |
if p == end: | |
return cnt | |
for nxt in connected[p]: | |
if nxt not in visited: | |
visited.add(nxt) | |
queue.append((cnt+1, nxt)) | |
return -1 | |
print(bfs(a, connected, b)) |
반응형
'프로그래밍 > 코딩테스트 문제풀이' 카테고리의 다른 글
[Python] SWExpertAcademy. 수영장 (0) | 2020.07.15 |
---|---|
[Python] 백준 12015. 가장 긴 증가하는 부분수열 2(LIS) (0) | 2020.07.14 |
[Python] 백준 5014. 스타트링크 (0) | 2020.07.09 |
[Python] 백준 1244. 스위치 켜고 끄기 (0) | 2020.07.08 |
[Python] 백준 19236. 청소년 상어 (0) | 2020.07.06 |