2 posts tagged “algorithm”
단어의 글자수는 3이고, 사전의 표제어는 다음과 같이 5개 있는 경우를 예로 들겠습니다.
사전에 몇 번 등장하는지 찾아야 할 대상 단어들 (이하 '문제단어'로 호칭) 은 2개라고 하겠습니다.
[사전의 표제어들]
abd
aed
efw
oli
fse
[사전에 몇 번 나오는지 알아내야 하는 단어들 = 문제단어들]
uiw
a(bel)(irdxq)
이제 uiw 과 a(bel)(irdxq) 가 각각 사전의 표제어에 몇 번씩 일치되는지를 알아내면 끝입니다.
답은 다음 형식으로 출력하면 됩니다. (XXX, YYY는 각각 사전에 등장한 횟수)
case #1 : XXX
case #2 : YYY
1. 망하는 풀이
사람이 사전을 찾을 때와 같은 식으로 푸는 방법입니다.
- 문제단어 각각에 대해
- 사전의 표제어들 각각과 일치하는지 검사하여 일치하면 일치횟수를 1 증가시킴
- 일치횟수를 출력
먼저 case #1 (즉 단어 'uiw') 의 경우는 간단합니다.
문제단어 'uiw'가 사전의 첫번째 표제어 'abd'와 일치하는지 검사하면 일치하지 않으니까 그냥 넘어가고, 사전의 두번째 표제어 'aed'와 일치하는지 검사하여 또 일치하지 않으니 그냥 넘어가고, ..., 마지막 표제어 'fse'와도 일치하지 않으니 넘어가고, 더이상 사전에 표제어가 없으면 끝입니다.
한번도 일치하지 않았으니까 일치횟수는 0이군요.
여기까진 문제가 없습니다.
다음 case #2 ( 단어 a(bel)(irdxq) ) 의 경우는 이런 방식으로 하면 다음과 같이 하게 됩니다.
문제단어가 확정된 것이 아니라 a(bel)(irdxq) 와 같이 여러 단어가 될 가능성이 있으므로 이를 풀어 보면 다음과 같은 단어조합이 가능합니다.
abi
abr
abd
abx
abq
aei
aer
aed
aex
aeq
ali
alr
ald
alx
alq
1*3*5 = 15개의 조합이 나왔습니다. 문제단어 a(bel)(irdxq) 는 표현상으로는 1개의 단어처럼 보이지만 실제로는 15개의 단어가 될 가능성을 가지는 것입니다.
이제 다음 풀이 방법을 적용시켜 보자면
- 문제단어 각각에 대해
- 사전의 표제어들 각각과 일치하는지 검사하여 일치하면 일치횟수를 1 증가시킴
- 일치횟수를 출력
문제단어 각각에 대해 사전 표제어 각각과 일치하는지 검사해야 하는데, 앞에서 문제단어가 1개가 아니라 15개가 되어 버렸습니다.
따라서
- 15개의 문제단어 각각에 대해
- 사전의 5개의 표제어들 각각과 일치하는지 검사하여 일치하면 일치횟수를 1 증가시킴
- 일치횟수를 출력
과 같이 계산해야 하므로, case #1에서 1개의 문제단어에 대해 사전의 5개의 표제어와 일치검사시에는 1*5=5번의 계산만 수행하면 되었던 것에 비해서 이번에는 15*5=75번의 계산이 필요합니다.
75번의 계산을 수행하면 결과는 '2회 일치'라는 것을 알 수 있습니다.
이 정도 표제어 수와 이 정도 조합의 단어까지는, 사람의 눈으로 보면 바로 몇 개가 일치하는지 보이죠.
이 정도까진 그냥 하면 되지 않냐 할 수 있는데, 단어의 길이가 10이고 문제단어가 다음과 같은 경우를 생각해 봅시다.
(qweasdzxcv)(poiuytrewq)(afdgs)(eydhcn)o(ethi)(bnvn)(asdfghjklm)(yt)(ghfjdk)
10 * 10 * 5 * 6 * 1 * 4 * 4 * 10 * 2 * 6 = 5,760,000
문제단어 1개가 실제로는 오백 칠십 육만개의 단어조합을 나타냅니다.
조합을 만들 때 가능한 경우의 수는 곱하기로 늘어나기 때문에 걷잡을 수 없이 커집니다.
이런 문제단어가 1000개라면? 오십 칠억 육천만개의 단어조합이 되지요.
그리고 사전의 표제어가 1000개라면? 오십칠억육천만 * 1000 번의 계산이 필요합니다.
계산할 수는 있겠지만 시간이 얼마나 걸릴지 알 수 없습니다. 그래서 망하는 풀이입니다.
2. 진짜 풀이
우선 문제를 다시 정리해 보죠.
다시 사전의 표제어를 살펴보겠습니다.
abd
aed
efw
oli
fse
그리고 문제단어들입니다.
uiw
a(bel)(irdxq)
case#2 인 단어 'a(bel)(irdxq)' 의 경우 다음과 같은 문제단어조합이 나오고, 이 중에 표제어와 일치하는 것은 abd와 aed의 2 개입니다.
abi
abr
abd
abx
abq
aei
aer
aed
aex
aeq
ali
alr
ald
alx
alq
그럼 이번엔 이렇게 풀어보겠습니다.
- 사전의 각 표제어에 대해서
- 문제단어와 일치하는지 검사하여 일치하면 일치횟수를 1 증가시킴
case #1은 뻔하니까 case #2 에 대해 풀어봅시다.
1) 1번째 사전 표제어 'abd' 가 문제단어 'a(bel)(irdxq)' 와 일치하는지를 검사.
- 첫번째 글자는 'a'로 같으니까 OK
- 두번째 글자는 사전표제어 'b' 가 문제단어의 '두번째 글자로 가능한 글자들 (bel)' 에 포함되니까 OK
- 세번째 글자는 사전표제어 'd' 가 문제단어의 '세번째 글자로 가능한 글자들 (irdxq)' 에 포함되니까 OK
- 마지막 글자까지 모두 일치했으니까 일치횟수 1 증가
2) 2번째 사전 표제어 'aed' 가 문제단어 'a(bel)(irdxq)' 와 일치하는지를 검사.
- 풀이는 똑같으니 생략함. 마지막 글자까지 모두 일치하니까 일치횟수는 또 1 증가하여 2가 됨.
3) 3번째 사전 표제어 'efw'가 문제단어 'a(bel)(irdxq)' 와 일치하는지를 검사.
- 첫번째 글자가 'e'와 'a'로 서로 다르니까 FAIL
- 두번째 글자부터는 볼 필요 없음
4) 4번째 사전 표제어 'oli'가 ....
- 풀이 생략. FAIL
5) 5번째 사전 표제어 'fse'가 ...
- 풀이 생략. FAIL
이와 같이 계산하여, case#2의 단어는 모든 사전 표제어에 대해 2번 일치함을 구했습니다.
이 경우에는 단어의 글자수가 늘어나고, 사전의 표제어 수가 많아지고, 문제단어 수가 많아져도 조합을 만들지 않기 때문에 소요시간이 기하급수적으로 증가하지 않습니다.
즉 이 문제 풀이의 핵심은 '조합을 만들지 않는 것' 에 있습니다.
좀 더 구체적인 사항으로는, 각 과정에서 다음과 같은 계산을 할 때
[ 사전표제어의 두번째 글자인 'b'가 문제단어의 두번째 글자로 가능한 (bel) 에 포함되는지 검사 ]
어떤 방법으로 검사하느냐에 따라 속도 차이가 납니다.
예를 들어 글자 'a' 가 (guiwpzanbmxc) 에 포함되는지를 검사할 때, (guiwpzanbmxc) 의 각 글자에 대해 a와 일치하는지를 순차적으로 검사할 수도 있습니다.
- 'g'가 'a'와 같은지 검사하여 아니니까 그룹 안의 다음 글자 'u'로 넘어가고
- 'u'가 'a'와 같은지 검사하여 아니니까 그룹 안의 다음 글자 'i'로 넘어가고
- ...
- 'z'가 'a'와 같은지 검사하여 아니니까 그룹 안의 다음 글자 'a'로 넘어가고
- 'a'가 'a'와 같은지 검사하여 같으니까 이번 그룹에 대해서는 일치한다고 판단.
이렇게 검사하면, 괄호 안의 글자들 중 a의 위치에 따라 계산속도가 달라집니다. a가 처음에 나오면 바로 일치한다고 판단할 것이고, 맨 마지막에 나오면 그때까지 계산을 반복해야 합니다.
이렇게 하지 않으려면 (guiwpzanbmxc) 를 그냥 텍스트나 배열로 만들어서 순차적으로 비교하는 것이 아니라, 다음과 같이 hash ( = map ) 의 형태로 만들어 놓고
{ 'g' => 1, 'u' => 1, ... , 'c' => 1 }
이 hash가 'a'라는 key를 가지는지 아닌지를 판단하면 됩니다.
( 이때 value는 뭐든 상관없습니다. value를 찾는 것이 목적이 아니라 해당 key가 존재하는가만 이용합니다. )
hash는 내부적으로 key를 빨리 찾기 위한 최적화된 자료구조를 가지고 있기 때문에 순차적인 계산을 수행하지 않으며, 그룹 내의 글자수가 많아져도 빨리 찾을 수가 있습니다.
예를 들어 hash가 내부적으로 b*tree로 이루어져 있을 경우, (abcdefghijklmnopqrstuvwxyz) 라는 26개의 글자를 가지는 그룹의 각 글자를 hash의 key로 만든 hash 안에 'q'가 있는지 없는지를 찾는 경우
- 1번째 계산 : 2개로 분리된 그룹들 (13개 / 13개) 중 q가 속할 수 있는 그룹이 선택됨
- 2번째 계산 : q가 속할 가능성이 있는 그룹이 다시 2개로 분리 (6개 / 7개) 되어 이 중 다시 q가 속할 수 있는 그룹이 선택됨
- 3번째 계산 : 다시 2개로 분리 (3개 / 4개) 되어 이 중 q가 속할 수 있는 그룹이 선택됨
- 4번째 계산 : 다시 2개로 분리 (2개 / 2개) 되어 이 중 q가 속할 수 있는 그룹이 선택됨
- 5번째 계산 : 마지막으로 분리된 글자수 2개의 그룹에 q가 있는지 검사.
이와 같은 식으로 처리됩니다.
이 방법의 좋은 점은, 그룹 내의 글자수가 100개 증가해도 계산해야 하는 횟수가 100번 증가하는 게 아니라는 점이지요.
여튼 이런 생각을 프로그램으로 만들면 다음과 같이 됩니다. (사실 후딱 짜고 나서 정리한 거지만) 딱 100줄이네요.
변수의 scope를 따져서 reference를 서브루틴으로 넘기거나 이런 건 하지 않았습니다. 돌아가는 데 집중한 코드입니다.
#!/usr/bin/perl
use strict;
use warnings;
use FileHandle;
my $dataFileName = 'A-small-attempt0.in';
my @dic; # 사전
my @message; # 사전과 대조해볼 단어들, 즉 case 들
my @messageInDicCount; # 각 case 가 사전의 표제어들 중 몇 개와 일치하는지. 프로그램의 목표는 이것을 구하는 것.
my $wordLength; # 단어의 길이. 사전의 표제어이든 사전과 대조해볼 단어든 모든 단어의 길이는 일정함.
my $dicEntryTotalNo; # 사전에 들어 있는 표제어의 수
my $messageTotalNo; # 사전과 대조해볼 단어들의 수
makeStructure();
calculate();
printout();
# 데이터파일을 읽어서 사전과 메시지 데이터구조를 만든다.
sub makeStructure {
my $ifh = new FileHandle( $dataFileName, 'r' );
my $linecount = 0;
my $dicAddedCount = 0;
my $messageAddedCount = 0;
while (<$ifh>) {
$linecount++;
chomp;
my $line = $_;
next if $line =~ m| \s* \# |x;
next if $line =~ m|^$|;
if ( $linecount == 1 ) {
( $wordLength, $dicEntryTotalNo, $messageTotalNo ) = split ' ', $line;
}
elsif ( $dicAddedCount < $dicEntryTotalNo ) {
push @{ $dic[$dicAddedCount] }, split '', $line;
$dicAddedCount++;
}
elsif ( $messageAddedCount < $messageTotalNo ) {
my $position = 0;
while ( $line =~ m/ ( \(\w+\) | \w ) /xg ) {
my $element = $1;
$element =~ s/\(//;
$element =~ s/\)//;
my @elArray = split '', $element;
for my $el (@elArray) {
$message[$messageAddedCount]->[$position]->{$el} = 1;
}
$position++;
}
$messageAddedCount++;
}
}
}
# 메시지 데이터구조 내의 각 메시지건들이 각각 사전의 표제어들 중 몇 개와 일치할 수 있는지를 구한다.
sub calculate {
$messageInDicCount[$_] = 0 for ( 0 .. $#message );
my $entryNo = 0;
for my $entry (@dic) {
my $messageNo = 0;
for my $message (@message) {
my $letterPosition = 0;
for my $entryLetter ( @{$entry} ) {
unless (
defined(
$message[$messageNo]->[$letterPosition]->{$entryLetter}
)
)
{
last;
}
$letterPosition++;
if ( $letterPosition == $wordLength ) {
$messageInDicCount[$messageNo]++;
}
}
$messageNo++;
}
$entryNo++;
}
}
sub printout {
for my $messageIndex ( 0 .. $#messageInDicCount ) {
$messageInDicCount[$messageIndex] = 0
unless defined $messageInDicCount[$messageIndex];
print "case #"
. ( $messageIndex + 1 )
. " : $messageInDicCount[$messageIndex]\n";
}
}
그리고 이 프로그램이 돌아갈 때 입력으로 받는 'A-small-attempt0.in' 파일 내용은 다음과 같습니다.
10 25 10
dheoyyidga
ebxfffvhqx
yjjpteklgp
yjwfawdkal
kgmjlupidf
feqrtmvgzd
vxnrcpqhzq
tlyhukdlsh
taljrgxoow
rjwgdyvtiw
ldjjmgvqrq
zkqmwjutzj
qqsmzvmwqw
vbzelmkgce
wdqopmxjgw
sypnmoiakb
xhcwmnkywm
esrvhghgsp
fmpuzdkkew
lbenzsdkqz
yxrqsawbjq
todikcmums
sxtwnuoqeh
pdeitylrzu
isklduprqc
lkbehqyxgf
(vzep)bzelmkgce
(mrz)(jmg)(vbl)(ac)(zhn)(mqs)(dhj)(qbg)(rux)(yci)
(rtgo)(nya)(zhlr)(ijw)(rzch)(vgh)(xado)(vlno)(opfg)(pwd)
(uwxyabcdfghijklmoprs)(ghijklmnpqrsuvwxabcdef)(wxyzabcdfgjklmnoprstuv)(knopqrstuvwxyzacdefghij)(cdefghijklmnoqrstuvwxyzab)(jklmnopqruvwzabcdfgi)(tvwxyzabcdfghijkmnopqrs)(pqrstuvxyzabcdefghjklmno)(efghijklmnopqrsuvwxyzbc)(abcefhijklmnopstuvwxy)
(wxzacdefhijklmnopqrsv)(klnopqrstuvwxyabcdfghi)(rstuvwxyabcdefgijlmnopq)(yzabdefghijklopqstvwx)(yzbcdefghijklmnopqrstuvwx)(wyzabcefghjklmnopqrstuv)(qrstuvwxzabcefhikmnp)(oprstuwxyzabcdfghijkmn)(xyzabcdefghijklmnoprsuvw)(klmnopqrstuxzabcdefghj)
(nuxy)(zerx)(raeh)(cdqs)(stbl)(sap)(djnw)(bdlq)(bejo)(qzd)
(stuvwxyzabcdefghiklmnopq)(stuvwxyzacdefghjlmnopq)(bcdefgijklmopqrstuvwyza)(xyzbcdefghiklmnpqrstvw)(qrstuvwxyzabcdfgijklmno)(ijklmnopqrsvwxyabcdfg)(gijklmopqrstuvwxyzacef)(abdefghijkmnopqrstuvwxyz)(abdefghijlnopqrstuvwxy)(ghijnoqrstuwxyzabcdef)
(fgku)(kmno)(pwbk)(ua)(zdim)(ydps)(koqy)(ahkn)(kvye)(adjw)
(tuwxyzabcdefghijklmnopqrs)(ghkmnopqtuvwxyzabcdef)(rstuvwxzacdeghijkmnoq)(lmopqstuvwxyzabdfghik)(bcdefghjklmnopqrstuvwxy)(ghijklmopqrstuvwxyzacdef)(xyzabcdefghiklmnpqrstvw)(stuvwxyzacdefghijklmnoqr)(tuvyabdefghjklmnopqs)(xyzabcdfgjklmnopqrtuvw)
프로그램의 수행 결과는 다음과 같습니다.
case #1 : 0
case #2 : 1
case #3 : 0
case #4 : 1
case #5 : 3
case #6 : 4
case #7 : 1
case #8 : 2
case #9 : 1
case #10 : 3
실제 code jam의 문제는, 입력파일이 이렇게 작지 않고
- 단어의 글자수는 15
- 사전의 표제어는 5000개
- 문제단어는 500개
입니다.
예를 들어 문제단어 하나가 이런 식입니다.
(xyabdefghiklnopqrstuvw)(tuvxyzabcdefijklmnopq)(yzacdefghijklmnopqrstuvx)(bcdfghiklmnopqrstuvxyza)(pqrstuvwxyzabdefghijklmno)(pqrsuvwxyzbcdeghijkmno)(rstuvxyabcdefijklmnopq)(jklmnopqstuvwxyzabcdegh)(cdefgijklmopqrstuvwxyza)(hjklmopqrstuvwxyzabcdefg)(wxyzabcdefgiklmnoqrsuv)(npqrstvwxyzabcdefghijklm)(efghjklmnopqrstvwxyzabcd)(xyzabcefghijklnopqrstuvw)(opqrstuvwxyzacdghijklmn)
이런 게 500개니까, 망하는 방법으로 풀면 언제 끝날 지 알 수 없겠지요.
여튼 요점은, '노가다도 잘 해야 한다' 입니다.
이번엔 문제풀이를 하나 해 보겠습니다.
여러 일들의 순서를 어떻게 정할 것인지, 하나의 일을 하기 위해 먼저 어떤 일들을 어떤 순서로 해야 하는지를 결정하는 문제인데요.
프로그램에서 쓰려는 것이 목적이지만 여기서는 컴퓨터 프로그램을 몰라도 아무 상관 없도록 설명할 것이니 누구든 읽을 수 있습니다. (정말?)
일단, 원래 어떤 문제인지는 다음 링크에 있습니다.:
http://blog.naver.com/anabaral/130041666110
anabaral 님이 일하다가 보니 문제를 해결할 뭔가가 필요해져서, 해결 방법을 만드셨습니다.
수학적인 방법으로 해결하셨습니다. (집합적인 사고방식 필요)
저는 이 문제를 처음 들었을 때 머릿속에 줄줄이 비엔나처럼 나열되는 구조가 떠올랐기 때문에
집합적인 방식이 아니라 그런 줄줄이 방식으로 문제를 풀었습니다.
그럼 시작해 볼까요?
문제로 바로 들어가기 전에 우선 기본부터 시작합시다.
1. 집을 지읍시다
'프로그램' 은 '수행할 일들의 목록' ( To-Do List ) 입니다.
당연히 컴퓨터 프로그램은 컴퓨터가 수행할 일들의 목록이죠.
여기선 컴퓨터에 대한 이야기를 할 것이 아니므로, 컴퓨터 프로그램이 아닌 그냥 할 일 목록에 대해서 생각해 봅시다.
집을 지으려면 여러 단계가 필요합니다. 땅을 사고, 기초공사를 하고, 뼈대를 세우고, 공구리를 치고 ㅋㅋ, 전기공사를 하고, 도배를 하고... 이걸 좀 단순화시켜서 집짓기 단계는 다음과 같다고 하겠습니다.
a. 토지 구입
b. 기초 공사
c. 벽 공사
d. 배관 공사
e. 전기 공사
f. 도배 장판 공사
이 단계들에는 어떤 걸 먼저 하고 어떤 건 그 다음에 해야 한다는 순서가 정해져 있습니다.
당연히 땅을 먼저 사고 기초공사를 해야지 남의 땅에 기초공사를 하고 집 지은 다음에 내가 집 지었으니 내땅이나 다름없는데 그냥 싸게 팔아라 그럼 안 되겠죠? (뭔가 다른 방법과 함께하면 은근히 먹힐 것 같기도 하지만 실생활에 사용하면 안되겠습니다.)
순서는 다음과 같다고 합시다. (실제로는 배관 깔고나서 전기공사를 하겠죠. 이건 예시일 뿐이니까 따지면 안됩니다.)
1. a.토지 구입
2. b.기초 공사
3. c.벽 공사
4. d.배관 공사, e.전기 공사
5. f.도배 장판 공사
여기서 4번째 순서에는 배관 공사랑 전기 공사가 같이 들어가 있습니다.
이것의 의미는 우선 3번째 순서인 벽 공사가 끝난 다음에 배관 공사도 할 수 있고 전기 공사도 할 수 있는데, 배관 공사랑 전기 공사 사이에는 정해진 순서가 없다는 의미입니다.
즉 벽 공사를 마친 다음에, 전기공사를 먼저 끝내고 배관공사를 할 수도 있고, 배관공사가 50% 완료된 시점에 전기공사를 시작할 수도 있고... 어떻게 해도 상관이 없다는 뜻입니다.
하지만 5번째 순서인 도배 장판 공사는 배관공사랑 전기공사가 둘 다 끝나야 시작할 수 있지요.
그럼 이걸 이제 그림으로 표현해 보겠습니다.
그림에서 화살표는 일의 진행방향이 아니라, 하나의 일을 수행하기 위해 먼저 끝내야 하는 조건을 가리킵니다.
다음은
b.기초공사 ← c.벽공사
'벽공사를 하기 위해선 먼저 기초공사가 끝나야 한다'의 의미이며
다음은
d.배관공사 ← f.도배장판공사
e.전기공사 ← f.도배장판공사
도배장판공사를 하기 위해선 먼저 배관공사도 끝나 있어야 하며, 전기공사도 끝나 있어야 한다는 의미입니다.
즉 XXX ← YYY 라는 것은, 'YYY의 선행(先行)조건은 XXX 이다' 의 의미입니다.
그림상에서 f.도배장판공사에서는 화살표가 두 개 뻗어나가 있으므로, f.도배장판공사 단계의 선행조건은 두 개인 것을 볼 수 있습니다.
이제 그림과 같이 집짓기의 단계가 정해졌는데, 그냥 그림이라고 계속 부를 순 없으니 이 그림을 '집짓기 조건 트리' 라고 부르겠습니다.
집을 짓기 위한 조건들 (어떤 단계보다 어떤 단계가 먼저 완료되어야 하는 조건들) 이 가장 윗 단계 (a.토지구입) 부터 가장 아래 단계 (f.도배장판공사) 까지 나뭇가지 뻗어나가는 것처럼 표현되었으므로 조건 트리라고 부릅니다.
(사실은 트리가 아니라 그래프인데... 이걸 프로그램으로 만들면서 사용한 단어가 트리여서 그냥 계속 트리로 가겠습니다.)
2. 샤워도 하고 TV도 봅시다.
집 짓는 순서는 정해졌는데, 샤워가 하고 싶네요. 집짓기 조건 트리에 샤워 단계를 추가해 봅시다.
일단 배관 공사만 끝나면 샤워를 할 수 있습니다. 전기공사가 안 되어서 깜깜해도, 도배장판공사가 안 된 상태여서 목욕탕 벽이 온통 시멘트라도 다 무시하고 샤워는 할 수 있습니다. 즉 전기공사나 도배장판공사는 샤워를 하기 위한 선행조건이 아닙니다.
그럼 그림은 이렇게 되지요.
샤워의 선행조건은 배관공사이므로, 배관공사만 끝나면 샤워를 할 수 있습니다.
도배장판공사가 끝났다면? 도배장판공사의 선행조건은 배관공사이므로, 도배장판공사를 했다는 것은 이미 그 전에 배관공사를 끝냈다는 것이고 당연히 샤워를 할 수 있습니다. 따라서 샤워단계에서 도배장판공사 단계로 화살표를 그을 필요가 없습니다.
그럼 TV 를 보려면 어떻게 해야 할까요?
일단 TV를 사 와야겠죠? 그런데 TV는 언제 사든 상관이 없습니다. 집 지을 땅을 사기 전에 미리 사 놨어도 되고, 기초공사 감독하다가 옆동네 하이마트에 잠깐 들러서 사 온 거라도, 아니면 TV를 보기 직전에 대리점에 전화주문해서 배달시켜도 아무 상관이 없습니다. 따라서 TV 구입은 그림상에 다음과 같이 나타낼 수 있습니다.
앞으로 조건트리 그림의 각각의 단계들을 '노드' (node)라고 부르겠습니다.
' h.TV 구입 ' 노드는 다른 노드들과 연관이 없으므로 덜렁 혼자 떨어져 있습니다.
이제 사 온 TV에 전기를 꽂고 TV를 시청하면 되는데, 여기서 좀 고민이 되네요.
기본적으로는 전기공사만 끝나면 TV 시청에 문제가 없지만, TV는 아무래도 부피가 큰 가전제품이다 보니 한번 자리를 잡으면 옮기기가 힘드니까 도배 장판 공사가 다 끝난 다음에 TV를 알맞은 위치에 설치한 후 볼 수 있도록 하는 것이 좋을 것 같기도 합니다.
이것은 선택의 문제이므로 어떤 것이 옳다고 할 수 없지요. 지금 저희집 TV는 구형이라 거의 옮긴다는 것이 불가능하므로 이를 기준으로 해서, 도배장판공사가 끝난 다음에 TV 시청을 할 수 있다고 해 보겠습니다.
TV시청노드는 선행노드 두 개 (h.TV 구입, f. 도배장판공사) 를 가리킵니다.
즉 TV시청을 위해 먼저 완료되어야 하는 선행조건이 두 개입니다. TV를 사 놓은 상태여야 하며, 도배장판공사가 끝나 있어야 합니다.
두 선행조건이 완료되었으면, 도배가 끝난 방 안에 TV를 가지고 들어와서 전기를 꽂고 TV를 볼 수 있습니다.
두 선행조건 (TV 구입, 도배장판공사) 사이에는 연관관계가 없으므로 어느 쪽이 먼저 완료되어야 한다는 조건은 없습니다. 단지 두 선행조건이 모두 완료된 다음에야 TV를 볼 수 있다는 것이 중요하지요.
이렇게 해서, 샤워와 TV시청을 위한 조건까지 포함된 조건 트리가 완성되었습니다.
3. 풀어야 하는 문제는 뭐지?
이제 문제를 해결해 봅시다. 문제는 두 가지입니다.
1) 조건트리에 논리적 문제가 없는지 어떤 방법으로 확인할 수 있는가?
집짓기 조건트리가 완성되었으니 이제 매번 집을 지을 때마다 조건트리를 기준으로 공사를 하게 됩니다.
그런데 조건트리 자체에 문제가 있다면 집 지을 때마다 문제가 발생하겠지요.
조건트리에는 여러 가지 문제가 발생할 수 있는데, 가장 대표적인 것으로 순환 (circulation) 이 발생하면 안 됩니다.
예를 들어 집을 지을 사람이 오묘한 정신세계의 소유자여서, 집터 기초공사의 첫 삽을 뜨기 전에 반드시 그 집에서 샤워를 하고 깨끗한 몸으로 우주의 기를 온몸으로 받아들여야 한다고 가정해 봅시다.
기초공사보다 먼저 샤워를 해야 하므로, 조건트리에서는 다음과 같이 기초공사 노드의 선행조건이 샤워 노드가 됩니다.
자 이제 문제가 발생했습니다.
기초공사하기전에 그 집에서 목욕재계를해야 하는데, 그러려면 먼저 배관공사가 되어 있어야 하고, 배관공사를 하려면 먼저 벽공사가 되어 있어야 하고, 벽공사를 하려면 기초공사가 끝나 있어야 하고, 기초공사를 하려면 먼저 목욕재계를 해야 합니다. 응? 영영 안끝나겠네요.
이렇게 순환이 발생한 것은 조건 자체가 잘못되었다는 뜻입니다. 이 조건을 따라서 집을 지으려다가는 땅만 사 놓고서 기초공사를 영영 못 들어가겠지요.
이 사람의 경우에는 아직 짓지도 않은 집에서 샤워를 해야 한다는 말도 안 되는 조건 때문에 순환이 발생했습니다. 따라서 공사 시작 전에 샤워를 해야 한다는 어긋난 신념을 버리고 샤워는 배관공사 후에 하도록 함으로써, 조건트리 그림상의 기초공사에서 샤워로 향하는 화살표를 제거하여 순환조건을 없앨 수 있습니다.
여기서 예로 든 집짓기 조건 트리는 간단하므로 이러한 문제가 있는지 바로 알 수 있지만, 실제로 조건들이 아주 많고 서로간의 관계가 복잡하면 (게다가 순환 오류가 아닌 다른 종류의 오류들도 있다면) 한눈에 어디가 문제인지 알기 힘들겠죠. 따라서 컴퓨터를 사용해서 조건트리에 문제가 있는지 없는지를 확인해야 합니다.
그런데 지금까지 본 것처럼 모든 것을 그림으로 그려서 표현하는 것은 사람에게나 가능하지 컴퓨터는 그림을 인식하지 못하므로 다른 방법을 사용해야 합니다.
따라서 조건트리의 오류 검증은 그냥 '눈으로 봐서 이상한 부분을 찾는다.' 는 원시적이고 인간적인 방법을 통해서가 아니라, '일관된 논리적 과정' 을 통해 이루어져야 합니다. 이 일관된 논리적 과정이 바로 프로그램이며, 결국 해결해야 할 첫번째 문제는 다음과 같습니다.
첫번째 문제 : 조건의 정합성 검사를 위한 프로그램 작성
주어진 조건 (예를 들어 집짓기 조건 트리) 에 오류가 있는지를 체크할 수 있어야 한다.
오류에는 여러 종류가 있을 수 있다. 순환 오류가 가장 기본적이다.
문제의 해결 과정은 뒤쪽의 프로그램 구현 부분에서 살펴보겠습니다.
여기서는 '사람이 눈으로 조건트리 그림을 보고 확인하는 것과 비슷한 과정을 수행하도록 프로그램을 만들었다' 라는 것까지만 이야기하고 넘어가겠습니다.
이제 풀어야 할 두번째 문제로 넘어갑니다.
2) 몇 개의 업무를 수행해야 하는데, 이를 위해 결국 어떤 업무들을 어떤 순서대로 실행해야 하는가를 무슨 방법을 통해 알 수 있는가?
문제를 한 문장으로 만들다 보니 좀 이상해졌는데, 다음과 같이 좀 구체적인 문제로 바꿔 보겠습니다.
(계속해서 집짓기 조건트리를 사용하겠습니다.)
문제1 : b.기초공사를 하려면 어떤 업무들을 어떤 순서로 수행해야 하는가?
풀이1 : b.기초공사의 선행조건은 a.토지구입입니다. 그리고 a.토지구입의 선행조건은 없습니다. 따라서 a.토지구입, b.기초공사 순으로 수행하면 됩니다.
답1 : a.토지구입, b.기초공사
문제2: i.TV시청을 하려면 어떤 업무들을 어떤 순서로 수행해야 하는가?
풀이2:
i.TV시청의 선행조건은 f.도배장판공사와 h.TV구입입니다.
선행조건이 두 개이므로 우선 f.도배장판공사에 대해 살펴보고 그 다음에 h.TV 구입을 살펴보겠습니다.
- i.TV시청보다 먼저 f. 도배장판공사가 끝나야 함. : [ f.도배장판공사, i.TV 시청]
- f.도배장판공사보다 먼저 d.배관공사와 e.전기공사가 끝나야 함. : [ d, e, f, i] (길어지니까 각 노드의 기호만 적습니다.)
* 실제 프로그램에서는 이런 경우 d, e를 동시에 처리하는 것이 아니라 d가 포함된 경로를 다 처리하고 그 다음에
e가 포함된 경로를 처리하게 됩니다만 여기서는 눈으로 보고 하는 거니까 그냥 한번에 처리합니다.
- d.배관공사와 e.전기공사보다 먼저 c.벽공사가 끝나야 함 : [c, d, e, f, i]
- 이런 식으로 a.토지구입까지 거슬러 올라가면 순서는 : [a, b, c, d, e, f, i]
이제 아직 처리하지 않은 i.TV시청의 선행조건인 h.TV구입에 대해 살펴보겠습니다.
- i.TV시청보다 먼저 h.TV구입이 완료되어야 함. ; [a, b, c, d, e, f, h, i]
여기서 i.TV 시청보다 먼저 h.TV구입이 이루어져야 하는데, h.TV 구입은 다른 노드들과의 연관관계가 없으므로 i.TV시청 앞에만 위치한다면 어디에 위치하든 상관이 없습니다. 그런데 i.TV시청 바로 앞에 위치하는 것이 가장 간단하고 특별히 다른 곳에 위치시킬 이유가 없으므로 h.TV구입은 i.TV시청 바로 앞에 위치시켰습니다.
해답2 : 최종 순서는 a,b,c,d,e,f,h,i
여기서는 문제를 풀 때 조건트리 그림을 보고 직접 손으로 따라가면서 풀었지만, 역시 컴퓨터는 그런 방법을 쓸 수는 없고 프로그램을 만들어서 사용해야 합니다. 따라서 두번째 문제는 다시 말하면 다음과 같습니다.
두번째 문제 : 주어진 업무 수행을 위해 최종적으로 수행해야 하는 업무 순서 목록을 구하는 프로그램 작성
주어진 업무가 몇 개이든 이를 수행하기 위해 어떤 업무들이 어떤 순서로 수행되어야 하는지를 구해야 함.
이제 문제 두 개는 다 주어졌고, 컴퓨터 프로그램이 아니라 사람의 눈과 머리와 손으로는 어떻게 풀 수 있는지도 보았습니다.
남은 것은 이것을 프로그램으로 어떻게 만드느냐입니다.
프로그램에 관심이 없으시면 여기까지만 보시고 끝내면 되겠습니다. 이 뒤로는 사람이 하던 걸 컴퓨터가 하도록 어떻게 바꾸느냐에 대한 이야기니까요.
4. 프로그램으로 만들자!
1) 조건 파일은 어떤 식으로 만들까?
앞에서 본 것처럼 조건트리를 그림으로 저장할 수는 없고 텍스트파일로 조건을 저장해야 합니다.
집짓기 조건에 대한 조건 파일 내용은 다음과 같은 형식으로 만들 수 있습니다.
a<-b
b<-c
c<-d
c<-e
d<-f
e<-f
d<-g
f<-i
h<-i
다음과 같은 내용으로 파일에 저장할 수도 있습니다만
a<-b<-c<-d<-f<-i
d<-g
c<-e<-f
h<-i
이런 식이라면 각 행마다 들어 있는 노드의 갯수도 달라서 이를 읽어서 처리하는 게 좀 복잡해 질 것 같습니다.
따라서 처리가 간단하도록 선행노드<-노드 의 꼴로 되어 있는 처음 방식으로 처리하겠습니다.
2) 조건 파일을 읽어서 조건트리를 만들자.
앞에서 만든 조건파일을 읽어서, 앞에서 계속 살펴본 집짓기 조건 트리에 해당하는 그 무엇을 구축해야 합니다.
그래야 그걸 가지고 정합성 체크도 하고, 순서대로 나열도 하고 할 수 있습니다.
조건파일을 읽어서 다음과 같은 자료구조가 되도록 처리합니다.
[c] <- d
[f, h] <- i
[null] <- a
[null] <- h
[b] <- c
[d, e] <- f
[d] <- g
[a] <- b
[c] <- e
여기서 [c]<-d 의 의미는 : HashMap의 원소 중 key가 String type의 "d" 인 요소의 value는 ArrayList<String>인데 원소를 "c" 하나만 가진 것을 말합니다.
마찬가지로 [d, e] <- f 의 의미는 : HashMap에서 f 를 키로 가지는 것은 value로 ' d, e 가 들어 있는 리스트' 를 가진다는 뜻입니다.
즉 집짓기 노드 트리 그림에서
- 각각의 노드가 HashMap의 하나의 요소가 되고,
- 요소의 key : 해당 노드의 id
- 요소의 value : 해당 노드의 선행 노드들의 id 들의 리스트
가 됩니다.
단방향 linked list 와 기본적으로는 비슷한데, 각 노드간의 연결을 간단히 처리한 버젼이라고 보시면 됩니다.
이렇게 조건정보가 담긴 HashMap을 하나 만들었습니다.
집짓기 조건 트리 그림과 방금 만든 HashMap은 생긴건 다르지만 결국 같은 놈입니다.
* 여기서 null 요소가 있는 것은 단순히 구현의 편의를 위해서입니다. 실제 최상위노드는 a와 h인데, a와 h 모두 각각 선행노드로 null을 가지게 됨으로써 최상위노드가 null 하나로 모인 것을 볼 수 있습니다.
3) 조건 트리의 정합성을 검증하자.
조건트리가 몽땅 하나의 HashMap에 들어 있으므로 이에 대해 검증을 수행합니다.
검증은 HashMap의 각 원소들, 즉 각 노드들에 대해 선행조건 화살표를 계속 따라가면서, 더이상 선행 노드가 없을 때까지 순환이 발생하지 않는지를 체크합니다.
이때 하나의 노드에서 여러 개의 선행노드를 가질 수 있으므로, 하나의 노드에서 시작하지만 따라가다 보면 여러 갈래로 나눠지는 경로가 여러 번 나올 수 있습니다. 이런 경우에 필요한 것은? 네, 재귀 탐색입니다.
집짓기 조건트리의 경우 f에서 시작한다면
- f - d - c - b - a 까지 체크해서 순환이 없으므로 통과
- 다시 f - e - c - b - a 까지 체크해서 순환이 없으므로 통과
와 같은 식으로 recursive traverse 방식으로 구현합니다.
실제로 프로그램을 돌려서 f 노드에 대한 정합성 체크를 하면서 찍어 본 결과는 다음과 같습니다.
Checking nodeId : f
f -> d
d -> c
c -> b
b -> a
OK. appeared nodeId : [f, d, c, b, a]
f -> e
e -> c
c -> b
b -> a
OK. appeared nodeId : [f, e, c, b, a]
더이상 선행노드가 없는 노드 (최상위 노드) 까지 이동하면서 순환이 발생하지 않았으므로 통과하는 것을 볼 수 있습니다.
이와 같은 식으로, 조건트리상에 존재하는 모든 노드를 시작점으로 하여 검증을 수행해서 모두 통과하면 조건트리에 오류가 없음을 알 수 있습니다.
* 여기서 하나의 팁이라면 :
f 노드에 대해 체크했을 때 appeared node id 목록이 [f, d, c, b, a]로 나온 것을 볼 수 있습니다. 이것은 f -> d -> c -> b -> a 로 완결되는 경로에는 오류가 없음을 의미하지요.
f노드에 대한 체크가 끝나고 c 노드에 대한 체크를 할 차례라고 가정해 봅시다.
그런데 c 노드는 이미 f노드 체크시 수행된 검증단계에서 성공된 경로에 포함되어 있습니다. 따라서 c 노드에 대해서는 검증을 수행할 필요가 없습니다.
또한 f노드에 대한 체크가 끝나고 g 노드에 대해 체크를 할 차례라고 가정해 보겠습니다.
원래대로라면 g->d->c->b->a 로 체크가 완료되는데, 마찬가지로 d 노드는 앞에서 f노드 체크시 성공한 경로에 포함됩니다.
따라서 g->d 까지만 수행하고 이후는 수행할 필요가 없습니다.
이렇게 검증을 수행하면 검증 수행 횟수가 많이 줄어들겠지요? 물론 이와 같은 생략이 적용될 수 있는 형태의 순환오류 검증의 경우에 대해서의 이야기입니다.
4) 특정한 노드들을 수행하기 위해 최종적으로 수행되어야 할 노드들의 순서있는 목록을 뽑자.
위에서 수행한 오류검증과 비슷합니다만, 오류검증은 트리를 따라 끝까지 가면서 오류가 없는지만 체크하면 되는 반면, 여기서는 최종적으로 나타나야 할 노드가 어떤 것인지, 그리고 그것이 목록의 어떤 위치에 있어야 하는지를 결정해야 합니다.
따라서 반드시 수행해야 하는 노드들 각각으로부터 시작해서 트리를 따라 끝까지 올라가면서, 최종 리스트를 계속해서 갱신해 줍니다. 이 작업이 끝났을 때의 최종 리스트가 진짜 최종 리스트가 됩니다.
(반드시 수행해야 하는 노드들을 따로 지정하지 않은 경우는 조건트리의 최하위 노드들을 우선 찾아서, 그 노드들 각각으로부터 시작해서 올라가면 조건트리상의 모든 노드들을 방문하게 됩니다.)
집짓기 조건에 대해 직접 프로그램을 돌리면서 찍어본 결과는 다음과 같습니다.
별도로 어떤 노드들이 꼭 필요하다고 지정하지 않고 돌렸으므로, 조건상에 존재하는 모든 노드들이 다 수행될 수 있도록 결과를 출력한 경우입니다.
각 행의 의미에 대한 설명을 붙였습니다. (====으로 시작하는 것이 설명). 여기서 [[1]] 과 같이 표시한 부분은 선행노드가 여러 개 있어서 분기가 발생했을 때 이 지점을 알아보기 쉽게 표시한 것입니다.
[f, i] <-- added : f, i ==== 최하위 노드 중 하나인 i부터 시작합니다. [[1]] i의 선행노드 중 하나가 f이므로 순서에 맞게 배치.
[d, f, i] <-- added : d before f ==== [[1-1]] f의 선행노드 중 하나는 d이므로 d를 f 앞에 배치.
[c, d, f, i] <-- added : c before d ==== d의 선행노드는 c이므로 c를 d 앞에 배치
[b, c, d, f, i] <-- added : b before c ==== 마찬가지
[a, b, c, d, f, i] <-- added : a before b ==== 마찬가지.
[null, a, b, c, d, f, i] <-- added : null before a ==== 마찬가지. null까지 도달했으므로 이 경로는 끝.
[null, a, b, c, d, e, f, i] <-- added : e before f ==== [[1-2]] f의 선행노드 중 나머지 하나인 e를 f 앞에 배치
[null, a, b, c, d, e, f, i] <-- ( passed : c, e) ==== e의 선행노드인 c를 e 앞에 배치하려고 했는데, 이미 c, e 둘 다 결과리스트에 들어 있고 순서도 맞게 되어 있음. 따라서 그냥 넘어간다.
[null, a, b, c, d, e, f, i] <-- ( passed : b, c) ==== 마찬가지
[null, a, b, c, d, e, f, i] <-- ( passed : a, b) ==== 마찬가지
[null, a, b, c, d, e, f, i] <-- ( passed : null, a) ==== 마찬가지. null까지 도달했으므로 이 경로는 끝.
[null, a, b, c, d, e, f, h, i] <-- added : h before i ==== [[2]] i의 선행노드 중 나머지 하나인 h를 i 앞에 배치
[null, a, b, c, d, e, f, h, i] <-- ( passed : null, h) ==== h의 선행노드가 null이므로 이 경로도 끝.
[null, a, b, c, d, g, e, f, h, i] <-- added : g after d ==== 최하위 노드 중 나머지 하나인 g에 대해 시작합니다. g 앞에 d를 배치해야 하는데, g는 결과리스트에 아직 없고 d는 이미 있으므로, d를 기준으로 그 바로 뒤에 g를 배치합니다.
[null, a, b, c, d, g, e, f, h, i] <-- ( passed : c, d) ==== g를 시작하로 하여 최상위까지 올라가는 경로. 배치하려는 c, d 노드 둘 다 결과리스트에 존재하고 순서도 바르게 되어 있으므로 그냥 pass.
[null, a, b, c, d, g, e, f, h, i] <-- ( passed : b, c) ==== 마찬가지
[null, a, b, c, d, g, e, f, h, i] <-- ( passed : a, b) ==== 마찬가지
[null, a, b, c, d, g, e, f, h, i] <-- ( passed : null, a) ==== g에서 시작한 경로도 끝.
이와 같이 하여 최종적으로 얻어진 수행 순서 목록은 다음과 같습니다. (이제 null 노드는 삭제합니다.)
[a, b, c, d, g, e, f, h, i]
마지막으로 모든 수행 결과 및 프로그램 구조를 첨부합니다.
1. 집짓기 조건에 따라 프로그램을 돌린 결과 전체
################################################
### Read a condition file into an ArrayList. ###
a <- b
b <- c
c <- d
c <- e
d <- f
e <- f
d <- g
f <- i
h <- i
##################################################
### Convert RAW condition into Condition Tree. ###
[c] <- d
[f, h] <- i
[null] <- a
[null] <- h
[b] <- c
[d, e] <- f
[d] <- g
[a] <- b
[c] <- e
################################################
### Validates Condition Tree. ###
Checking nodeId : d
d -> c
c -> b
b -> a
OK. appeared nodeId : [d, c, b, a]
Checking nodeId : i
i -> f
f -> d
d -> c
c -> b
b -> a
OK. appeared nodeId : [i, f, d, c, b, a]
f -> e
e -> c
c -> b
b -> a
OK. appeared nodeId : [i, f, e, c, b, a]
i -> h
OK. appeared nodeId : [i, h]
Checking nodeId : a
OK. appeared nodeId : [a]
Checking nodeId : h
OK. appeared nodeId : [h]
Checking nodeId : c
c -> b
b -> a
OK. appeared nodeId : [c, b, a]
Checking nodeId : f
f -> d
d -> c
c -> b
b -> a
OK. appeared nodeId : [f, d, c, b, a]
f -> e
e -> c
c -> b
b -> a
OK. appeared nodeId : [f, e, c, b, a]
Checking nodeId : g
g -> d
d -> c
c -> b
b -> a
OK. appeared nodeId : [g, d, c, b, a]
Checking nodeId : b
b -> a
OK. appeared nodeId : [b, a]
Checking nodeId : e
e -> c
c -> b
b -> a
OK. appeared nodeId : [e, c, b, a]
Validation Passed without errors.
################################################
### Makes arranged node list. ###
[f, i] <-- added : f, i
[d, f, i] <-- added : d before f
[c, d, f, i] <-- added : c before d
[b, c, d, f, i] <-- added : b before c
[a, b, c, d, f, i] <-- added : a before b
[null, a, b, c, d, f, i] <-- added : null before a
[null, a, b, c, d, e, f, i] <-- added : e before f
[null, a, b, c, d, e, f, i] <-- ( passed : c, e)
[null, a, b, c, d, e, f, i] <-- ( passed : b, c)
[null, a, b, c, d, e, f, i] <-- ( passed : a, b)
[null, a, b, c, d, e, f, i] <-- ( passed : null, a)
[null, a, b, c, d, e, f, h, i] <-- added : h before i
[null, a, b, c, d, e, f, h, i] <-- ( passed : null, h)
[null, a, b, c, d, g, e, f, h, i] <-- added : g after d
[null, a, b, c, d, g, e, f, h, i] <-- ( passed : c, d)
[null, a, b, c, d, g, e, f, h, i] <-- ( passed : b, c)
[null, a, b, c, d, g, e, f, h, i] <-- ( passed : a, b)
[null, a, b, c, d, g, e, f, h, i] <-- ( passed : null, a)
Result node list in order:
[a, b, c, d, g, e, f, h, i]
2. 프로그램 구조
다음 그림과 같습니다. 클릭해서 별도페이지로 본 다음 다시 클릭해서 최대화해야 잘 보일 듯하네요.
업무를 수행하는 클래스는 다음의 4개입니다.
- TwoColumnFileReader : 각 행이 '선행노드<-노드' 형태로 구성된 조건파일을 읽어서 단순히 그대로 리스트로 변경합니다.
- TreeMapper : 위에서 변경한 리스트를 조건트리 (즉 HashMap) 로 매핑합니다.
- TreeCircularValidator : 조건트리에 순환오류가 없는지 체크합니다.
- TreeArranger : 조건트리의 조건에 따라 수행될 노드의 순서있는 목록을 만듭니다.
TreeCondition 클래스는 위 4개의 업무 수행 클래스를 가지면서 (즉 use), 동시에 다음을 멤버변수로 가지고 있습니다.
- contidionTreeMap : 조건트리 (실제 구현은 HashMap 형태)
- validationFailedSet : 조건트리 검증시 오류가 발생했다면 어느 구간에서 발생했는지가 여기에 저장됨
- arrangedNodeList : TreeArranger에서 수행할 노드 목록을 만든 결과가 여기에 저장됨.
이제 앞서 살펴본 4개의 업무수행 클래스를 순서대로 사용합니다. (Reader, Mapper, Validator, Arranger)
- Reader, Mapper를 사용 : 조건파일을 읽어서 조건트리를 구성하여TreeCondition 클래스의 conditionTreeMap에담습니다.
- Validator를 사용 : conditionTreeMap에 담긴 조건트리의 정합성을 체크합니다. 이상이 있을 경우 이상이 있는 부분을 validationFailedSet에 담습니다.
- Arranger : 반드시 사용할 노드의 목록 및 조건트리를 사용하여, 최종 수행 노드 리스트를 만들어서 arrangedNodeList에 담습니다.
이제 arrangedNodeList에 담긴 결과 순서대로 작업을 수행하면 됩니다~~~
소스는 중구난방이라 안 올립니다. ㅋㅋ 테스트하는 클래스 소스만 올리겠습니다.
package test.liquidbird.ordering;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;import liquidbird.ordering.arranger.Arranger;
import liquidbird.ordering.arranger.TreeArranger;
import liquidbird.ordering.condition.ICondition;
import liquidbird.ordering.condition.TreeCondition;
import liquidbird.ordering.mapper.Mapper;
import liquidbird.ordering.mapper.TreeMapper;
import liquidbird.ordering.reader.Reader;
import liquidbird.ordering.reader.TwoColumnFileReader;
import liquidbird.ordering.validator.TreeCircularValidator;
import liquidbird.ordering.validator.Validator;public class OrderingTester {
public static void main(String[] args) {
// 조건 객체
ICondition condition = new TreeCondition();
// 조건 객체에 조건파일 리더를 설정
Reader reader = new TwoColumnFileReader();
//reader.setSource("condition_d.txt");
reader.setSource("condition_build_a_house.txt");
condition.setReader(reader);
// 조건파일 리더가 읽은 조건을 조건트리로 매핑하는 매퍼를 조건객체에 설정
Mapper mapper = new TreeMapper();
condition.setMapper(mapper);
// 조건객체의 리더와 매퍼를 순차적으로 실행시켜서 조건객체 내부에 조건트리를 생성해 넣는다.
condition.build();
// 조건 객체에 조건 정합성 검사기를 설정
Validator validator = new TreeCircularValidator();
condition.setValidator(validator);
// 정합성 검사 수행. 통과하지 못하면 더이상 진행하지 않는다.
if ( condition.validate() == false ) {
System.out.println("\nSTOPPED due to the validation check failure.");
System.exit(1); // ㅋㅋ 확실한 죽음을 선사한다. giving an instant death.
}
// 조건에 따라 노드를 순서대로 나열하는 arranger를 구현하는 적절한 구현체를 선택.
Arranger arranger = new TreeArranger();// 최종결과목록에 반드시 포함되어야 할 노드의 목록을 arranger에 세팅. 필수사항 아님.
// ( 세팅하지 않으면 모든 노드를 사용하도록 동작한다. )
List<String> wantedElements = new ArrayList<String>();
// a,f 요소는 결과에 반드시 포함되어야 하는 경우에 대한 예. 나열 순서는 무관.
String[] wanted = new String[] {"a","f"};
Collections.addAll(wantedElements, wanted);
// 아래 행을 주석처리하면 모든 노드에 대해 순서를 구하도록 동작한다.
//arranger.setWantedElements( wantedElements );// 조건객체에 arranger를 세팅
condition.setArranger(arranger);
// arrange 수행
condition.arrange();
}
}
아 길군요. 적는 데 시간도 오래 걸렸네요.
