하는 문제인데요.. 각 노드는 입력으로 받은 좌표(x,y)에서,(x+1,y),(x,y+1),
(x+1,y+1) 4개 중 한 개를 선택해서 실제 노드 좌표로 정할수있어요.
저는 각 노드마다 4개의 부울변수를 두어서 해당 점에서 다른 노드로 길이 w인 엣지를 둘수 있는가 없는 가를 체크해서, 4개의 위치에서 연결되는 노드에 길이가 w가 아니면 거짓으로 체크합니다. 그래서 모든 노드에 대해서 이러한 체크를 해서, 모든 노드 중에 단 해가라도 4개의 부울 변수가 거짓이면은 해당 그래프가 그릴 수 없다고 판단했어요..
점이 중복될 경우를 고려하지 않으신 것 같아요... 예를들어서 노드 3개가 있고, 1번 노드와 3번 노드가 2번의 (x+1, y+1) 에 연결해야 서로 '3'이라는 distance를 얻을 수 있다고 생각해봅시다. 위의 알고리즘대로 돌리게 되면 이는 yes가 뜨지 않을까요?...
제가 생각해봤는데요.. 신장 그래프를 이용하는게 맞을 까요? 노드 끼리 서로 영향을 주는 이유가, 노드간에 싸이클이 존재하기 때문인데, 신장 그래프는 위 문제조건에서 노드간에 서로 독립적인 요소이기때문에 주어진 입력에 맞는 엣지의 길이들을 가지는 신장 그래프를 구하게 되면 각 노드별로 정점이 고정되게 될 것이고, 신장 그래프에 포함되지 않은 엣지들 즉, 싸이클을 이루는 엣지들에 대해서 입력값에 주어진 엣지를 만들 수 있는지 확인 하면 되지 않을까요..??
juhosung
2010 ACM - daejon에서 나온 g번 문제를 혼자 풀어보고 있는데,
너무 어렵네요..
acm 이게 문제 링크고요..
혹시 해결하신분 있나요..??
문제를 정리하자면,
입력으로 들어온 각 그래프의 노드의 좌표정보를 받아서,
입력으로 들어온 각 노드간의 엣지 거리를 만족하는 그래프를 만들 수 있는가
하는 문제인데요.. 각 노드는 입력으로 받은 좌표(x,y)에서,(x+1,y),(x,y+1),
(x+1,y+1) 4개 중 한 개를 선택해서 실제 노드 좌표로 정할수있어요.
저는 각 노드마다 4개의 부울변수를 두어서 해당 점에서 다른 노드로 길이 w인 엣지를 둘수 있는가 없는 가를 체크해서, 4개의 위치에서 연결되는 노드에 길이가 w가 아니면 거짓으로 체크합니다. 그래서 모든 노드에 대해서 이러한 체크를 해서, 모든 노드 중에 단 해가라도 4개의 부울 변수가 거짓이면은 해당 그래프가 그릴 수 없다고 판단했어요..
이렇게 해서 샘플 입력은 잘 되는데, 계속 롱앤써뜹니다.. 뭐가 문제일까요..
11년 전