BST 문제 검토 부탁 드립니다. kwangswei 아, 정말 한 번에 깔끔하게 푸는 문제가 없네요 ㅠ.ㅠ BST 문제 입니다. BST 조건을 만족하는 트리인지 체크하는 문제인데요. 제 알고리즘은 다음과 같습니다. 먼저 Input 을 모두 받습니다. Root 를 찾습니다. ( 어떤 노드로부터 참조되지 않는 노드를 찾음.) In-order 순회를 하면서 key 값 비교 시 이전에 순회한 key 값을 저장해두었다가 비교를 합니다. 이 때 키 값이 이전 값보다 작거나 같으면 바로 false 를 반환합니다. 모두 순회를 이상 없이 돌았으면 true 를 반환합니다. 예제 문제는 답이 잘 나옵니다. 뭔가 고려하지 못한 부분이 있는 것 같은데 조언 부탁 드립니다. 감사합니다. #include <stdio.h> bool IsBST( int (*node)[3], int cur, int last) { int result = true; // visit left if ( node[cur][0] != 0 ) if ( IsBST( node, node[cur][0], last ) == false ) return false; // visit me if ( node[cur][2] <= last ) return false; last = node[cur][2]; // visit right if ( node[cur][1] != 0 ) if ( IsBST(node, node[cur][1], last) == false ) return false; return true; } int main(){ int T; scanf("%d", &T); while ( T-- ) { int flag[101] = {0,}; int node[101][3] = {0,}; int N; scanf("%d", &N); for ( int i = 1; i <= N; i++ ) { scanf("%d %d %d", &node[i][0], &node[i][1], &node[i][2]); flag[node[i][0]] = 1; flag[node[i][1]] = 1; } // find root. int root; for ( int i = 1; i <= N; i++ ) { if ( flag[i] == 0 ){ root = i; break; } } printf("%s\n", IsBST(node, root, -1) == true ? "YES" : "NO"); } return 0; } 11년 전
6개의 댓글이 있습니다. Being 다음부터는 [[problem:BST]] 이렇게 링크를 걸어 주세요~ BST 11년 전 link kwangswei 아, 네 수정해놓았습니다. ^^;; 11년 전 link Being last 파라미터를 통해 마지막 방문한 노드의 번호를 기억하셨는데, C/C++에서 기본적으로 함수 호출시에는 call by value라는 점이 문제가 되겠네요. 11년 전 link Kureyo BST의 조건이 왼쪽의 서브트리의 모든 애들보다도 값이 커야하고 오른쪽의 서브트리의 모든 애들보다도 값이 작아야하는데 이거는 부모자식간단순 비교라서 안되는거 아닐까요?ㅅ? 5 / 3 / \ 1 6 이 데이타에 대해 BST라고 나오시면 안되실거같습니다 11년 전 link kwangswei 아! 이런 멍청한 실수를!! 함수를 1개로 합치면서 빼먹었네요 & 를.... Being 님 조언대로 고쳐서 해결했습니다! 감사합니다. 11년 전 link kwangswei @Kureyo 부모 자식 간 단순 비교는 아니고, In-order 를 사용해서 순회하면 정렬이 되니까, 정렬이 어긋나는 지점이 있는지를 보는 방식을 사용했습니다~! 11년 전 link 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
kwangswei
아, 정말 한 번에 깔끔하게 푸는 문제가 없네요 ㅠ.ㅠ
BST 문제 입니다.
BST 조건을 만족하는 트리인지 체크하는 문제인데요.
제 알고리즘은 다음과 같습니다.
예제 문제는 답이 잘 나옵니다.
뭔가 고려하지 못한 부분이 있는 것 같은데 조언 부탁 드립니다.
감사합니다.
11년 전