교재 28장 단어제한 끝말잇기 문제에 관하여

  • Hyogon
    Hyogon

    책 코드28.5의 주석을 보면
    indegree는 i로 시작하는 단어의 수 이고
    outdegree는 i로 끝나는 단어의 수인데
    책 코드를 보면

    int a = words[i][0]- 'a';
    int b = words[i][words[i].size() - 1] - 'a';
    graph[a][b].push_back(words[i]);
    adj[a][b]++;
    outdegree[a]++;
    indegree[b]++;

    이렇게 되어있는데 이코드에서의 의미는
    outdegree가 시작하는 단어의 수고
    indegree가 끝나는 단어의 수 아닌가요??

    +845page에서
    //이때 오일러 서킷의 존재 조건이 만족되려면 a에서 나가는
    간선이 들어오는 간선보다 하나 많고,b는 들어오는 간선이
    나가는 간선보다 하나많고,//

    이 이야기는 오일러 트레일의 존재 조건 만족에 대한 설명
    아닌가요?


    5년 전
1개의 댓글이 있습니다.
  • hyunhwan
    hyunhwan

    그림 28.7의 (b)에서도 보면 dog라는 단어에 대한 간선의 방향이 해서 d라는 노드에서 나가고, g라는 노드로 가는 방향임을 볼 수 있는데, 이를 토대로 보면 질문하신데로 outdegree와 indegree의 정의가 맞으며, 주석은 잘못되어 보입니다.


    5년 전 link

  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.