문제 14, 에르되시 수 (Erdos Numbers)

책 정리/Programming Challenges : 알고리즘 트래이닝 북

문제 14, 에르되시 수 (Erdos Numbers)

최익필 2009. 12. 8. 00:59

PC/UVa ID : 110206/10044

사설

문제 풀기는 한 2주 쯤 된거 같다. 에르되시 수를 풀기 위해선 "최단 경로" 알고리즘이 필요 했기에 이 부분이 제일 막혔다. 1주 가량 지하철을 타오면서 실마리를 풀어서, 바로 코딩 작업에 착수 해서 완성하였다.

실마리는 "한번 갔던 길은 되돌아 가지 않고, 갈 수 있는 길로 계속 가면 된다." 아직 이 방법밖에 모르겠으므로, 다른 문제 풀때 한번 알아보자.

개요

에르되시 수 부터 알아야 하는데, 책보다는 에르되시의 수 에서 한번 보길 권한다. 쉽게 설명하면, 에르되시와 같이 논문 쓰면 에르되시의 수는 1이다. 만약 에르되시 수 1인 사람과 같이 논문을 썻다면 나는 에르되시의 수 2가 된다. 마찬가지로 2인 사람과 같이 논문을 썻다면 나는 3이 된다.

입력

첫째 행에는 시나리오 갯수가 들어간다. 각 시나리오에는 논문 데이터베이스와 이름 목록으로 구성 된다.
첫째 행 뒤에는 P와 N이라는 자연수를 입력 받는다. P는 논문의 수이고, N은 에르되시 수를 알고 싶은 사람들의 수이다.
그 다음 줄에는 논문 데이터 베이스가 입력 되며, 이때 저자도 같이 다음의 양식으로 입력 된다.
Smith, M.N., Martin, G., Erdos, P.: Newtonian forms of prime factor matrices
Erdos, P., Reisig, W.: Stuttering in petri nets
3번의 입력이 끝나면, 에르되시 수를 알고 싶은 사람의 이름을 N 개 만큼 입력 받는다.

출력

백문의 불허 일견, 링크로 대체한다.
http://www.programming-challenges.com/pg.php?page=downloadproblem&probid=110206&format=html

-- 에르데시의 수
-- UVa ID: 10044
-- ikpil.com
-- 2009.11.26
ErdosName = "Erdos, P."
ErdosInfinityNum = -1

-- 논문의 저자를 만드는 함수
function CreateWriter( Name )
	Writer = {}
	Writer.Name = Name
	Writer.Treatise = {}
	return Writer
end

-- 논문들을 DB화 시킨다.
function CreateDatabase( Treatises )
	-- Step 4. 논문의 제목을 기준으로 한 Database를 구축 한다.
	Database = {}
	for i, Treatise in pairs(Treatises) do
		-- Step 4-1. 저자들과 논문 제목을 분리 시킨다.
		wirters_end, subject_start = string.find( Treatise, ": " )
		wirters = string.sub( Treatise, 1, wirters_end - 1  )
		subject = string.sub( Treatise, subject_start + 1 )

for Name in string.gmatch( wirters, "%u%l+, [%u.]+" ) do
			Database[subject] = Database[subject] or {}
			table.insert( Database[subject], Name)
		end
	end

return Database
end

-- 논문DB를 이용하여 모든 저자들을 뽑아 온다.
function CreateWriters( Database )
	Writers = {}
	for TreatiseSubject, WritersOfWriters in pairs( Database ) do
		for i, Name in pairs( WritersOfWriters ) do
			Writers[Name] = Writers[Name] or CreateWriter( Name )
			if nil == Writers[Name].Treatise[TreatiseSubject] then
				Writers[Name].Treatise[TreatiseSubject] = TreatiseSubject
			end
		end
	end

return Writers
end

-- 지정한 이름의 에르되시 수를 찾고 리턴해 준다.
function GetErdosNum( Database, Writers, Writer, Count, WritersOfTreatise )
	Count = Count or 1
	WritersOfTreatise = WritersOfTreatise or {} -- 논문을 같이 쓴 저자들
	SearchWriters = {} -- 논문을 누구와 같이 썻는지 찾아야할 저자들

-- 1. 논문 DB에서 논문 제목으로 저자들을 뽑아 온다
	-- 2. 뽑아온 저자들 중 이미 찾은 저자는 제외 시킨다.
	-- 3. 제외되지 않은 저자들은 더 찾아야봐야 하므로, 찾아야할 저자들에 저장한다.
	for i, Subject in pairs(Writer.Treatise) do
		for j, WriterOfTreatise in pairs(Database[Subject]) do
			if nil == WritersOfTreatise[WriterOfTreatise] then
				WritersOfTreatise[WriterOfTreatise] = Writers[WriterOfTreatise]
				SearchWriters[WriterOfTreatise] = Writers[WriterOfTreatise]
			end
		end
	end

-- 자기 자신의 이름은 이미 위에서 목록을 뽑았으므로, 제외 시킨다.
	SearchWriters[Writer.Name] = nil

-- 찾아야할 대상이 한개도 없다면 그냥 끝낸다.
	if 0 == table.size(SearchWriters) then
		return ErdosInfinityNum
	end

-- 에르되시가 있다면 현재 카운터를 리턴한다.
	if nil ~= SearchWriters[ErdosName] then
		return Count
	end

-- 현재 에르되시 수를 못 찾았다면, 다른 저자들의 에르되시 수를 계산한다.
	-- 이때 찾은 에르되시 수는 모아 둔다. 왜냐하면 제일 작은 에르되시 수를 찾아야 하니까.
	ErdosPack = {}
	for k, SearchWriter in pairs( SearchWriters ) do
		erdosnum = GetErdosNum( Database, Writers, SearchWriter, Count + 1, WritersOfTreatise )
		table.insert( ErdosPack, erdosnum )
	end

-- 정렬
	table.sort( ErdosPack )

-- 끝의 수가 -1 이라면, 모두 -1 이므로, 에르되시를 찾지 못하였음
	if ErdosInfinityNum == ErdosPack[#ErdosPack] then return -1 end

-- 이 코드는 0 이상의 에르되시 수를 갖는 값을 리턴하기 위하여 만들었다.
	-- 순차로 돌다가 -1이 아닌 값을 찾으면, 그 수가 제일 작은 에르되시 수이다.
	for i, v in pairs( ErdosPack ) do
		if ErdosInfinityNum ~= v then return v end
	end
end

-- 테이블 내부 값을 보기 위해(디버깅 용)
function table.view( t )
	for i, e in pairs( t ) do
		print( i, e )
	end
end

-- 테이블의 크기를 알기 위해
function table.size( t )
	size = 0
	for i, e in pairs( t ) do
		size = size + 1
	end
	return size
end

function main()
	-- Step 1. 시나리오 넘버를 입력 받는다.
	-- 시나리오는 독립적인 상황이라는 의미를 갖고 있다.
	--ScenarioNum = tonumber(io.read())

-- test code
	ScenarioNum = 1

LoopCount = 1
	while LoopCount <= ScenarioNum do

-- Step 2. P의 값과 N의 값을 입력 받는다.
		-- P는 논문의 갯수이며, N은 에르데시 수를 계산할 사람들의 수이다.
		--inputPnN = io.read()
		PnN = {}
		--for Number in string.gmatch( inputPnN, "%d+" ) do
		--	Number = tonumber(Number)

--	if nil == Number then
		--		print("ERROR : PnN in INPUT")
		--		return
		--	end

--	table.insert( PnN, Number )
		--end
		-- test code
		table.insert( PnN, 4 )
		table.insert( PnN, 3 )

if 2 ~= #PnN then
			print("ERROR PnN size is not 2 : " .. #PnN )
			return
		end

-- Step 3. 표준 입력을 통해 모든 논문 작성자와 논문제목들을 입력 받는다.
		Treatises = {} -- 논문들
		--for i = 1, PnN[1], 1 do
		--	table.insert(Treatises, io.read() )
		--end

-- test code
		table.insert( Treatises, "Smith, M.N., Martin, G., Erdos, P.: Newtonian forms of prime factor matrices" )
		table.insert( Treatises, "Erdos, P., Reisig, W.: Stuttering in petri nets" )
		table.insert( Treatises, "Smith, M.N., Chen, X.: First oder derivates in structured programming" )
		table.insert( Treatises, "Jablonski, T., Hsueh, Z.: Selfstabilizing data structures" )

Database = CreateDatabase( Treatises )
		Writers = CreateWriters( Database )

-- Step 7. 에르되시의 수가 보여질 사람의 이름을 받는다.
		ViewNames = {}
		-- for i = 1, PnN[2] do table.insert( ViewNames, io.read() ) end
		-- test code
		table.insert( ViewNames, "Smith, M.N." )
		table.insert( ViewNames, "Hsueh, Z." )
		table.insert( ViewNames, "Chen, X." )

-- Step 8. 최종 출력하고 시나리오를 끝낸다.
		for i, Name in ipairs( ViewNames ) do
			ErdosiNum = GetErdosNum( Database, Writers, Writers[Name] )
			print(Name, ErdosInfinityNum == ErdosiNum and "Infinity" or ErdosiNum )
		end

LoopCount = LoopCount + 1
	end
end

main()

느낀점

주석은 반드시 달자
변수명은 오래 생각해도 되니, 꼭 잘 정하자
함수로 뺼 수 있으면 함수로 빼자
끝까지 놓지 말자, 반드시 풀릴테니까.

저작자표시 (새창열림)