matrix[i]가 과정 i를 등록하는 데 필요한 선행 과정 목록을 나타내는 2D 행렬이 있다고 가정합니다. 이제 모든 과목 수강이 가능한지 여부를 확인해야 합니다.
따라서 입력이 행렬 =[[1],[2],[]]와 같으면 출력은 True가 됩니다. 코스 2, 코스 1, 코스 0을 차례로 선택할 수 있기 때문입니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
함수 dfs()를 정의합니다. 이 시간이 걸립니다
-
vis[i]가 참이면
-
거짓을 반환
-
-
chk[i]가 참이면
-
참을 반환
-
-
vis[i]:=참
-
행렬[i]의 각 j에 대해 수행
-
dfs(j)가 거짓이면
-
거짓을 반환
-
-
-
vis[i]:=거짓
-
chk[i]:=참
-
참을 반환
-
기본 방법에서 다음을 수행하십시오 -
-
vis:=행렬의 행 개수와 크기가 같은 목록이고 처음에는 모두 거짓입니다.
-
chk:=행렬의 행 개수와 동일한 크기의 목록이고 처음에는 모두 거짓입니다.
-
행렬의 행 수까지 범위 0에 있는 i에 대해
-
dfs(i)가 거짓이면
-
거짓을 반환
-
-
-
참을 반환
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
class Solution: def solve(self, matrix): vis=[False for _ in matrix] chk=[False for _ in matrix] def dfs(i): if vis[i]: return False if chk[i]: return True vis[i]=True for j in matrix[i]: if not dfs(j): return False vis[i]=False chk[i]=True return True for i in range(len(matrix)): if not dfs(i): return False return True ob = Solution() matrix = [ [1], [2], [] ] print(ob.solve(matrix))
입력
matrix = [ [1], [2], [] ]
출력
True