728x90
문제 설명
버스정류장 N개가 있습니다. 각 정류장에는 1번부터 N번까지의 번호가 매겨져 있습니다. 2차원 배열로 주어진 정류장 표지판(signs)에는 A번 정류장에서 B번 정류장으로 가는 버스가 있다면 1, 없다면 0으로 표시되어 있습니다.
예를 들어, 3개의 버스정류장이 있을 때
로 표시된 정류장 표지판이 주어진다면,
- 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으로 표시하려고 합니다.
위 예시에서는
이 되며. 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입니다.
입출력 예
| 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
문제의 예시와 같습니다.
입출력 예 #2
- 1번 정류장->3번 정류장->2번 정류장으로 갈 수 있으므로, 1행은 [0,1,1]이 됩니다.
- 2번 정류장->3번 정류장->2번 정류장으로 갈 수 있으므로, 2행은 [0,1,1]이 됩니다.
- 3번 정류장->2번 정류장->3번 정류장으로 갈 수 있으므로, 3행은 [0,1,1]이 됩니다.
#코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
from collections import deque
'''
각 지점마다 deq에 도착 가능한 지점들을 넣어준다.
하나씩 꺼내어서 도착 가능한 지점들에서 도착할 수 있는 새로운 지점들을 탐색하고 deq에 추가해준다.
deq가 남아있을 때까지 이를 반복해준다.
'''
def solution(n,signs):
for start in range(n):
deq = deque()
for j in range(len(signs[start])):
if signs[start][j] == 1:
deq.append(j)
while deq:
temp = deq.popleft()
for end in range(len(signs[temp])):
if signs[temp][end] == 1 and signs[start][end] == 0:
signs[start][end] = 1
deq.append(end)
return signs
|
cs |
반응형