onlyhim   1년 전

제가 짠 코드는 다음과 같습니다.

만들어진 트리를 x,y좌표에 위치한다고 가정하여 각 노드별로 x,y좌표를 지정해주었습니다.

makeorder함수를 통해 중위순회로 노드를 왼쪽에서 부터 오른쪽까지 xpos배열에 저장합니다. (각 노드의 x좌표를 결정)

bfs함수를 통해 각 노드의 y좌표를 ypos배열에 저장합니다.(각 노드의 y좌표를 결정)

이후에 각 노드별로 높이에 해당하는 최대 값을 찾아 각각 max, min 배열에 저장합니다.

그 다음에 max[i] - min[i]를 통해 최대값을 찾아냅니다.


해결을 위한 반례나 지침부탁드리겠습니다.

감사합니다.

chogahui05   1년 전

(1) makeorder함수를 통해 중위순회로 노드를 왼쪽에서 부터 오른쪽까지 xpos배열에 저장합니다. (각 노드의 x좌표를 결정)

(2) bfs함수를 통해 각 노드의 y좌표를 ypos배열에 저장합니다.(각 노드의 y좌표를 결정)

(3) 이후에 각 노드별로 높이에 해당하는 최대 값을 찾아 각각 max, min 배열에 저장합니다.

아이디어는 맞는 거 같은데.. bfs 함수를 써도 되고. 그런데. 잠재적인 문제가 있습니다.


http://stackoverflow.com/quest...

일단 위 답변 참고해 주세요. 정수형은 아시다시피 1byte가 넘어가는 자료형인데.

이걸 0과 -1이 아닌 다른 값으로 초기화를 했다? 잠재적인 문제점이 있다고 보면 됩니다.

(그도 그럴 것이 memset은 byte 단위로 작업을 수행하니까요.)

chogahui05   1년 전

여기서 찾은 memset 함수인데요. 리눅스 깔아보셔서 내부 구조 보시는 거 추천드립니다.

버전에 따라서 내부 구조가 다를 수가 있으니까요.

페도라, 우분투. 등등.. 깔아보셔서 직접 보시는 게 좋습니다.


http://lxr.free-electrons.com/...

딱히 볼 건 없고요. 제가 님 코드를 단순화 시켜서 테스트 해 보니. 


10001로 memset를 한 경우에는

437918234로 초기화가 되네요. 이건 00011010 00011010 00011010 00011010 이죠.

10001은 00000000 00000000 00100111 00011010이 되는데.. 당연히 의도와는 맞지 않은 결과죠.


아래 코드에서 10번째 ~ 14번째 줄이 핵심이라고 보심 될 거 같네요.

당연한 이야기겠지만, memset에 관한 질문 역시 엄청나게 들어오는데. (커뮤니티에)

나중에 고생하시지 마시고, 내부 구조를 명확하게 아는 게 좋을 듯 싶네요.

생각보다 memset를 잘 쓰는 게 굉장히 어려운 편입니다.


다음에, bfs를 활용한 아이디어. 좋아 보이는데요.

기능이 복잡해 졌을 때, 구현을 할 수 있는가가 문제이지요.

아마 제가 봤을 땐 memset 때문에 WA를 받으셨을 가능성이 있어보이지만..


중위 순회. 아이디어 좋았습니다. 그리고 이건 재귀호출로 구현되죠. 아시다시피.

트리의 너비 = 중위순회 ___ , 높이 = 재귀호출 한 함수의 __ 일까요? 이 __을 채우는 게 핵심입니다.

이 2개의 빈칸을 채우신 거 같은데.. (대충이나마 아시는 듯 싶더군요.)


그렇다면 초기화 문제 정도가 있겠죠.. ~_~;;

한 가지 확실한 건, 트리의 너비는 bfs를 쓰지 않고도 얼마든지 구현할 수 있다는 겁니다.

onlyhim   1년 전

chogahui05


자세하고 친절한 답변 정말 감사드립니다. 댓글이 늦었네요 ㅠㅠ

행복하세요

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