| [ QuizWit ] in KIDS 글 쓴 이(By): Convex (4ever 0~) 날 짜 (Date): 1997년12월12일(금) 17시18분18초 ROK 제 목(Title): Re: # NxN grid spanning trees 음 제가 문제를 좀 간략하고 애매모호하게 냈나보네요. grid라는 것은 모눈종이 같은 것이고.. N x N grid는 가로 N개 세로 N개의 직선을 그어 교차하는 N^2(N제곱)의 점과 이어지는 선들만 뽑아내면 됩니다. 가령 2x2는 입 '구' (한자로) 모양이 되겠고 3x3는 밭 '전' 모양이 되겠지요. 4x4 는 *--*--*--* 형태가 되겠고.. | | | | *--*--*--* | | | | *--*--*--* | | | | *--*--*--* spanning tree라는 것은 그 grid 상의 선 중에서 N^2-1 개의 선만 뽑아 만들되 cycle 없고 연결된 상태로 있게 만드는 subgraph입니다. 가령 2X2 grid 에서는 *--* *--* *--* * * 요렇게 4개가 있을거고, | | | | | | * * *--* *--* *--* 그렇다면 3x3 grid상의 spanning tree는 모두 몇개인가 하는 것이죠. 그리고 일반적으로 NxN grid에 대한 공식이 있는가 하는게 문제. --,--`-<@ 매일 그대와 아침햇살 받으며 매일 그대와 눈을 뜨고파.. 잠이 들고파.. Till the rivers flow up stream | Love is real \|||/ @@@ Till lovers cease to dream | Love is touch @|~j~|@ @^j^@ Till then, I'm yours, be mine | Love is free | ~ | @@ ~ @@ |