[Python3] 버스 여행

버스정류장 N개가 있습니다. 정류장에는 1번부터 N번까지의 번호가 매겨져 있습니다.

2차원 배열에서 A번 정류장에서 B번 정류장으로 가는 버스가 있다면 O, 없다면 X로 표시합니다.

예를들어 3개의 버스정류장이 있을 때
X O X
X X O
O X X
와 같이 표시하면

• 1번 정류장에서 2번정류장으로 갈 수 있음(첫 번째 줄의 O)
• 2번 정류장에서 3번정류장으로 갈 수 있음(두 번째 줄의 O)
• 3번 정류장에서 1번정류장으로 갈 수 있음(세 번째 줄의 O)

이 표를 이용해서 버스를 계속 갈아타서라도 갈 수 있는 정류장을 모두 표시하는 2차원 배열을 리턴하세요.

위의 표와 같이 1번에서 2번 정류장으로, 그리고 2번에서 3번 정류장으로 가는 버스가 있다면, 한 번 갈아타면 1번에서 3번 정류장으로 갈 수 있다는 뜻이 됩니다.

busTour 함수를 통해 모든 정류장에서 출발해서 도달할 수 있는지를 표시하는 배열을 리턴하세요.

입력이

X O X
X X O
O X X

라면 다음과 같이 리턴하면 됩니다.

O O O
O O O

O O O

 tryhelloworld.co.kr에 Level6문제이다. 이곳 에서 풀 수 있다.

 친구의 친구는 친구 라는 친밀도 계산 문제에서 종종 볼 수 있는 알고리즘이다. 사람이라면 그래프를 그려서 풀텐데 컴퓨터는 그림으로 계산하기 힘드므로 숫자로 바꿔서 해보자.

def busTour(map):
    num_result = []  # 숫자결과
    result = []  # 최종결과

    g = dict()  # 그래프그리기 ex) {0: [1], 1: [2], 3: [0]}
    for i in range(len(map)):
        temp = []
        for j in range(len(map)):
            if (map[i][j] == 'O'):
                temp.append(j)
                map[i][j] = 'X'
        g[i] = temp

    for station in range(len(map)):
        bus = []  # 버스노선
        temp_result = set()
        done = set()  # 완료한곳은 가지않기
        bus.append(station)
        while (bus):  # 버스가 갈곳이 남아있으면
            station2 = bus.pop(0)  # 환승
            for x in g[station2]:  # 환승후 갈곳
                if x not in done:
                    temp_result.add(x)
                    bus.append(x)
                    done.add(x)
        num_result.append(list(temp_result))

    for i in range(len(map)):  # 숫자형식의 노선도를 O,X로 변환
        temp2 = []
        for j in range(len(map)):
            if (j in num_result[i]):
                temp2.append('O')
            else:
                temp2.append('X')
        result.append(temp2)

    return result


# 아래는 테스트로 출력해 보기 위한 코드입니다.
print(busTour([['X', 'O', 'X'], ['X', 'X', 'O'], ['O', 'X', 'X']]))

[['O', 'O', 'O'], ['O', 'O', 'O'], ['O', 'O', 'O']]

Process finished with exit code 0