211122 - 버스 여행

◾ 버스 여행

문제

버스정류장 N개가 있습니다. 각 정류장에는 1번부터 N번까지의 번호가 매겨져 있습니다. 2차원 배열로 주어진 정류장 표지판(signs)에는 A번 정류장에서 B번 정류장으로 가는 버스가 있다면 1, 없다면 0으로 표시되어 있습니다.

예를 들어, 3개의 버스정류장이 있을 때

	0	1	2
0	0	1	0
1	0	0	1
2	1	0	0

로 표시된 정류장 표지판이 주어진다면,

• 1번 정류장에서 2번 정류장으로 갈 수 있습니다. (A=1, B=2)
• 2번 정류장에서 3번 정류장으로 갈 수 있습니다. (A=2, B=3)
• 3번 정류장에서 1번 정류장으로 갈 수 있습니다. (A=3, B=1)

또한, 버스를 갈아타는 것이 가능합니다. 예를 들어, 위 예시에서는 1번에서 2번 정류장으로, 그리고 2번에서 3번 정류장으로 가는 버스가 있으므로, 한 번 갈아타서 1번에서 3번 정류장으로 갈 수 있습니다. 버스는 여러번 갈아타는 것이 가능합니다.
우리는 이 표를 이용해서 특정 정류장 A에서 특정 정류장 B로 갈 수 있는지 판단하여, 갈 수 있으면 1, 갈 수 없으면 0으로 표시하려고 합니다.

위 예시에서는

	0	1	2
0	1	1	1
1	1	1	1
2	1	1	1

이 되며. A번째 줄의 B번째 숫자는 A 정류장에서 B 정류장으로 갈 수 있는 지의 정보를 나타냅니다. 단, 출발지와 목적지 사이에서 적어도 하나의 버스를 타는 경우에만 1로 표시합니다.

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

---

입력

• N : 100 이하의 자연수
• 정류장 표지판(signs)는 2차원 배열이며, 1 또는 0으로만 이루어져 있습니다. 단, i번째 줄의 i번째 숫자는 항상 0입니다.

출력

• 특정 정류장 A에서 특정 정류장 B로 도달할 수 있는지 표시

입출력 예

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]]

---

◾ 풀이

1. 해설

• BFS를 이용해 각 정류장에서 도달할 수 있는 정류장을 탐색한다.
• 시작 정류장에서 가능한 정류장에 방문 표시하고 덱에 추가한다.
• 덱이 빌때까지 반복하며 정류장들을 방문한다.
• 방문한 정류장들을 answer에 추가한다.

---

2. 프로그램

1. 시작 정류장을 기준으로 visited 초기화
2. 방문 가능(e == 1)하며 방문하지 않은(visited[idx] == 0) 경우
   • 방문 표시
   • 덱 추가
3. 덱이 빈경우 visited를 answer에 추가
4. 모든 정류장을 기준으로 위 동작을 반복한다.

# 코드
from collections import deque

def solution(n,signs):
    answer = []

    def bfs(start):         # bfs로 시작 정류장에서 가능한 정류장 탐색
        visited = [0] * n   # 방문하는 정류장 저장용 리스트
        q = deque([start])
        while q:
            v = q.popleft()
            for idx, e in enumerate(signs[v]):
                # e == 1 : 현재 정류장에서 갈 수 있는 정류장이라는 의미
                # visited[idx] == 0 : 아직 방문하지 않은 정류장
                if e == 1 and visited[idx] == 0:
                    visited[idx] = 1    # 방문 표시
                    q.append(idx)       # 정류장 추가
        answer.append(visited)          # 방문 가능한 정류장 추가

    for v in range(n):
        bfs(v)

    return answer