[Python] 프로그래머스 Lv 4 - 버스여행

즐거운 BFS 문제

프로그래머스 Lv 4 버스여행 문제

 

알고리즘

갈 수 있는 루트가 있는지 버스가 많아질수록 일반적인 확인은 어렵다고 판단,
BFS를 사용하기로 했다.

조금 걱정된 부분은 버스가 많을때 visited가 커지면 복잡도 면에서 걱정이 되었는데
set으로 처리를 해서 복잡도 면에서 조금 이득을 보는 구성을 사용하였다.

코드

from collections import deque
def can_reach_bfs(start, end, signs):
    visited = set()
    queue = deque()
    queue.append(start)
    while queue:
        next = queue.popleft()
        visited.add(next)
        for i in range(len(signs)):
            if i == end:
                # 여기서 돌아가는게 목적이면 처리됨(cycle의경우)
                if signs[next][end] == 1:  
                    return 1
            # cycle을 빠져나와야 하는 경우엔 간 적 없는데로 가야함.
            elif i not in visited and signs[next][i] == 1:
                queue.append(i)
                visited.add(i)
    return 0
def solution(n,signs):
    answer = [[0 for _ in range (n)] for _ in range (n)]
    for x in range(n):
        for y in range(n):
            answer[x][y] = can_reach_bfs(x, y, signs)
    
    return answer

 

그런데 무려 플로이드-와샬 알고리즘을 써서 푸는 풀이가 있는 모양이다....
3중 반복문으로 끝내버렸어....