convert7342   3년 전

1 ~ 67번줄 코드는 시간초과 코드이고

71번줄 부터의 코드는 AC가 뜬 코드입니다.

인접 리스트를 이용해 a, b 를 입력받아 [b] 인덱스에 a를 푸시해주는 방식으로

모든 노드에 대하여 dfs를 이용해 탐색했습니다.

두 코드의 차이는 dfs마다 visit를 true로 이용 한 뒤 false로  그때마다 바꿔주는 것과 memset 을 이용해 visit를 초기화 하는 차이가 있습니다.

memset을 이용했을 때는 시간초과가 발생하지 않았는데

윗부분의 코드에서 제가 발견하지 못한 오류가 있을지 여쭤봅니다.

hellogaon   3년 전

주어진 그래프가 단방향 그래프이고 위의 방법과 같이 코드를 작성했을 경우

dfs가 동작할 때 O(N)보다 많은 시간이 걸릴 수도 있습니다.

6개의 노드에 아래와 같은 단방향 간선으로 그래프가 연결되어 있을 때,

1 -> 2

2 -> 3

3 -> 4

1 -> 5

1 -> 6

5 -> 2

6 -> 2

dfs가 들리는 정점 번호는

1 -> 2 -> 3 -> 4 이후 2, 3, 4에서 visit을 다시 false로 만들어주어

5 -> 2 -> 3 -> 4

6 -> 2 -> 3 -> 4 와 같이 2, 3, 4번 노드를 다시 방문할 것이라 생각이 드네요.

convert7342   3년 전

친절한 답변 감사드립니다.

댓글을 작성하려면 로그인해야 합니다.