글 읽기 - 2250 트리의 높이와 너비 질문드립니다.(코드 상세 설명 있습니다)

onlyhim 7년 전 0

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

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

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

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

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

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

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

감사합니다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
vector<vector<pair<int, int>>> adj;
queue < int >q;
int parent[10010] = {};
bool visit[10010] = {};
int xpos[10010] = {};
int ypos[10010] = {};
int x = 1;	int y = 1;
void makeorder(int root){
	if (adj[root].front().first == -1 && adj[root].front().second == -1){
		xpos[root] = x++;
		return;
	}
	if (adj[root].front().first != -1)	makeorder(adj[root].front().first);
	xpos[root] = x++;
	if (adj[root].front().second != -1)	makeorder(adj[root].front().second);
}
// 각 노드의 x좌표값을 저장하는 함수
void bfs(int root){
	queue<int> tmp;
	visit[root] = 1;
	q.push(root);
	ypos[root] = y++;
	while (!q.empty()){
		while (!q.empty()){
			int here = q.front();
			if (here == -1){
				q.pop();
				continue;
			}
			q.pop();
			for (auto i : adj[here]){
				if (i.first != -1){
					int left = i.first;
					tmp.push(left);
					visit[left] = 1;
				}
				if (i.second != -1)	int right = i.second; {
					int right = i.second;
					tmp.push(right);
					visit[right] = 1;
				}
			}
		}
		while (!tmp.empty()){
			ypos[tmp.front()] = y;
			q.push(tmp.front());
			tmp.pop();
		}
		y++;
	}
}
// 각 노드의 y좌표값을 저장하는 함수
int main() {
	int n, a, b, c, root;
	cin >> n;
	adj.resize(n + 1);
	for (int i = 1; i <= n; i++){
		scanf("%d %d %d", &a, &b, &c);
		adj[i].push_back(make_pair(b, c));
		parent[b] = parent[c] = a;
	}
	for (int i = 1; i <= n; i++)	if (!parent[i])	root = i;	//부모 찾기
	makeorder(root);	// 노드를 왼쪽부터 배열 xpos에 저장하기
	bfs(root);	// 높이 찾아주기
	int ans = 0;
	int max[10010] = {};
	int min[10010] = {};
	memset(min, 10000, sizeof(int)* 10010);
	for (int i = 1; i <= n; i++){
		if (!max[ypos[i]] || max[ypos[i]] < xpos[i])	max[ypos[i]] = xpos[i];
        // max[i] 배열은 높이가 i인 노드중 가장 오른쪽에배치된 노드번호를 기록합니다.
		if (!min[ypos[i]] || min[ypos[i]] > xpos[i])	min[ypos[i]] = xpos[i];
        // min[i] 배열은 높이가 i인 노드중 가장 왼쪽에배치된 노드번호를 기록합니다.
	}
	int maxdep = 0;
	for (int i = 1; i <= n; i++)	if (ypos[i] > maxdep)	maxdep = ypos[i];
    //최대 높이 찾아주기
	int ans1 = 0;
	int ans2 = 0;
	for (int i = 1; i <= maxdep; i++)	{
		if (max[i] - min[i] +1> ans1)
		{
			ans1 = max[i] - min[i]+1;    // 최대 x값 - 최대y값
			ans2 = i;    // y좌표
		}
	}
	cout << ans2 << ' ' << ans1 << endl;
}

chogahui05 7년 전 0

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

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

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

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

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

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

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

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

chogahui05 7년 전 0

여기서 찾은 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를 쓰지 않고도 얼마든지 구현할 수 있다는 겁니다.

void *memset(void *v_src, int c, __kernel_size_t n)
 {
          char *src = v_src;
          uint32_t *i_src;
          uint32_t w32 = 0;
  
          /* Truncate c to 8 bits */
          c = (c & 0xFF);
  
          if (unlikely(c)) {
                  /* Make a repeating word out of it */
                  w32 = c;
                  w32 |= w32 << 8;
                  w32 |= w32 << 16;
          }
  
          if (likely(n >= 4)) {
                  /*
                  switch 구문 생략.
                  */
  
                  i_src  = (void *)src;
  
                  /* Do as many full-word copies as we can */
                  for (; n >= 4; n -= 4)
                          *i_src++ = w32;
  
                  src  = (void *)i_src;
          }
  
          /* Simple, byte oriented memset or the rest of count. */
          while (n--)
                  *src++ = c;
  
       return v_src;
}

onlyhim 7년 전 1

chogahui05

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

행복하세요

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

문제

문제

출처

ICPC

2250 트리의 높이와 너비 질문드립니다.(코드 상세 설명 있습니다)

onlyhim 7년 전 0

chogahui05 7년 전 0

chogahui05 7년 전 0

onlyhim 7년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말