버스여행 (python)

생각보다 간단한 문제, input이 작아 어렵지 않게 풀 수 있다.
DFS를 이용하여 차례로 도착할 수 있는 곳 탐색, 연쇄작용을 하는 유형

👀 깃헙 소스

문제설명

버스정류장 N개가 있습니다. 각 정류장에는 1번부터 N번까지의 번호가 매겨져 있습니다. 2차원 배열로 주어진 정류장 표지판(signs)에는 A번 정류장에서 B번 정류장으로 가는 버스가 있다면 1, 없다면 0으로 표시되어 있습니다.또한, 버스를 갈아타는 것이 가능합니다. 예를 들어, 위 예시에서는 1번에서 2번 정류장으로, 그리고 2번에서 3번 정류장으로 가는 버스가 있으므로, 한 번 갈아타서 1번에서 3번 정류장으로 갈 수 있습니다. 버스는 여러번 갈아타는 것이 가능합니다.
A번째 줄의 B번째 숫자는 A 정류장에서 B 정류장으로 갈 수 있는 지의 정보를 나타냅니다. 단, 출발지와 목적지 사이에서 적어도 하나의 버스를 타는 경우에만 1로 표시합니다.

정류장 표지판(signs)이 매개변수로 주어질 때, 특정 정류장 A에서 특정 정류장 B로 도달할 수 있는지를 표시하여 return 하는 solution 함수를 완성해 주세요. 위 예시의 경우는 [[1,1,1],[1,1,1],[1,1,1]]로 return 하면 됩니다.

N : 100 이하의 자연수

입출력 예

n	signs				answer
3	[[0,1,0],[0,0,1],[1,0,0]]	[[1,1,1],[1,1,1],[1,1,1]]
3	[[0,0,1],[0,0,1],[0,1,0]]	[[0,1,1],[0,1,1],[0,1,1]]

솔루션

각 지점마다 temps에 도착 가능한 지점들을 넣어준다.
하나씩 꺼내어서 도착 가능한 지점들에서 도착할 수 있는 새로운 지점들을 탐색하고 temps에 추가해준다.
temps가 남아있을 때까지 이를 반복해준다.

방법 1) DFS / 스택 사용 O(N+E)

# 파이썬
def solution(n, signs):
    for start in range(n):
        temps = [i for i, pos in enumerate(signs[start]) if pos]
        while temps:
            temp = temps.pop()
            for end, pos in enumerate(signs[temp]):
                if pos and signs[start][end] == 0:
                    signs[start][end] = 1
                    temps.append(end)
    return signs

방법 2) 플로이드 워셜 이용 O(n^3)

# 파이썬
def solution(n, signs):
    for temp in range(n):
        for start in range(n):
            for end in range(n):
                if signs[start][temp] == 1 and signs[temp][end] == 1 :
                    signs[start][end] = 1
    return signs