busyhuman   5년 전

루트노드의 개수를 출력했는데 이 방법이 아닌가요?

jh05013   5년 전

3 2
1 2
2 3

jh05013   5년 전

취소합니다. 정점이 0부터 시작이군요.

jh05013   5년 전

3 3
0 1
1 0
2 1

busyhuman   5년 전

이거 코드를 다 뜯어서 다른 방법으로 짜야하나요?

leehosu01   5년 전

busyhuman   5년 전

힌트 좀 주실 수 있나요 머리가 안돌아가네요 ..

onlyhim   5년 전

제가 해결한 방법 입니다.

요구사항 : 주어진 그래프에서 트리 혹은 사이클이 몇개인지 출력한다.

  1. 각 트리의 루트노드부터 BFS로 해당 트리의 노드를 모두 방문처리하고 정답에 +1
  2. 이외에 방문한 적이 없으면 사이클이므로 사이클 갯수만큼 +1

busyhuman   5년 전

@onlyhim pc방에서 반쯤 정신놓고 하니까 풀려있네요. . 배그해야겠다하고 제출했는데

xowns9418   5년 전

@onlyhim 답변주신거에 대해서 "트리의 루트 노드 부터 BFS 탐색"이라고 하셧는데   혹시, 루트노드를 어떤 식으로 찾으셧나요??  루트노드만 찾으면 그 점부터 BFS로 방문체크해주고(바이러스 1개) 방문안된 노드의 갯수를 세어서 답을 구할 수 있을거 같은데..


onlyhim   5년 전

@xowns9418

안녕하세요. 노드의 크기만큼 배열 parent를 선언하고 -1로 초기화합니다. 

그리고 두 입력 a,b가 주어졌을때, 즉 a->b일때 parnet[b]=a로 값을 수정합니다.

모든 입력을 받은 후에 parent[i]==-1이면 해당노드가 트리의 루트인것을 알 수 있습니다.

감사합니다.

busyhuman   5년 전

@xowns9418

입력받을 때 부모노드가 있는 노드를 전부 체크해주면 남은것들은 모두 루트노드가 됩니다.

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