문제 2 : 지뢰 찾기(minesweeper)

PC/UVa ID : 110102/10189, 인기도 : A, 성공률 : 높음, 레벨 : 1]

말 그대로 지뢰 찾기를 만들라는 것인데, * 가 지뢰고 . 가 안전 지대라 했을 때, 4 x 4 의 지뢰밭이 다음과 같다고 하자. 그러면 오른쪽 처럼 출력되게 하는 프로그램을 만들라 가 이번 문제의 목표이다.

입력

첫번째로 지뢰 밭의 크기를 가로 row X 세로 col 을 받되, 각 길이는 0 ~ 100 사이 값이여야 한다. 또한 0 0 이 입력 되었을 경우 프로그램은 종료되어야 한다.

출력

각 지뢰밭에 대해 Field #x: 라 적혀있는 메세지를 출력 하고, x 필드는 1번부터 시작해 사용자가 끝낼때까지 1씩 올라 간다. 자세한 것은 예제를 보는게 좋을 것이다.

예제

입력
4 4
*....
....
.*..
....

Field #1:
*100
2210
1*10

3 5
**...
.....
.*...

Field #2:
**100
33200
1*100

0 0
정상 종료

총평

루아 입출력 함수 사용법 익히는데 많은 시간이 걸렸다. 여담으론 입력 스트림을 날려버리는 함수가 있으면 매우 좋겠다란 생각을 하게 된다. 스트림을 제어 할 수 있는 언어, 이런 언어가 참 유용하지 않을까란 생각도 한다. 이번 문제에 대해서 이야기 하자면, if 를 쓰지 않고도 충분히 처리 할 수 있다면, 안쓰는게 훨씬 좋지 않을까 한다. 왜냐하면, 코드 분량이 더 늘어나고, 논리적으로 생각 해야 되는 것도 더 늘어나기 때문이다.

최초 if 로 양 사이드 끝이라면, 상하 사이드 끝이라면, 이라는 식으로 의사코드를 짜다가, 코드가 너무 더러워 져서, if 없이 짤 수 있지 않을까? 란 생각을 했다. 다음과 같은 알고리즘을 생각하고, 루아로 만들게 된 것이다.

여담
회사 다니면서, 책 보는 량이 무척 줄었으므로, 포스팅도 하루에 한개씩만... ㅋ

문제 풀이 소스

function create_minefield_table( a )
	local t = { }

local i = 1
	while i <= a do
		t[#t + 1] = { }
		i = i + 1
	end

return t
end

function input_data_pattern_check( s, col )
	-- 길이 체크

if string.len( s ) ~= col then
		print( "길이 체크에서 걸림" )
		return false
	end

-- 문자 체크
	local index = 1
	while index <= col do
		capture_char = string.sub( s, index, index )
		-- * 나 . 인지 체크
		if false == ( capture_char == "*" or capture_char == "." ) then
			return false
		end
		index = index + 1
	end

return true
end

function insert_minefield_to_table( minefield_tb, minefield, col )
	local index = 1
	while index <= col do
		table.insert( minefield_tb, string.sub( minefield, index, index ) )
		index = index + 1
	end
end

function regist_mine_to_minefield_table( minefiled_tb, s, col )

if false == input_data_pattern_check( s, col ) then
		return false
	end

insert_minefield_to_table( minefiled_tb, s, col )
end

-- hint_number를 기록한 hint_table을 만든다.
function create_hinttable( row, col )
	local hint_table = { }
	local iii = 1
	while iii <= row + 2 do
		hint_table[ iii ] = { }

local jjj = 1
		while jjj <= col + 2 do
			hint_table[ iii ][ jjj ] = 0
			jjj = jjj + 1
		end
		iii = iii + 1
	end

return hint_table
end

function regist_hintnumber_to_hinttable_impl( target_tb, row, col )
	row = row
	target_tb[row][col] = target_tb[row][col] + 1
	target_tb[row][col + 1] = target_tb[row][col + 1] + 1
	target_tb[row][col + 2] = target_tb[row][col + 2] + 1

row = row + 1
	target_tb[row][col] = target_tb[row][col] + 1
	target_tb[row][col + 1] = target_tb[row][col + 1] + 1
	target_tb[row][col + 2] = target_tb[row][col + 2] + 1

row = row + 1
	target_tb[row][col] = target_tb[row][col] + 1
	target_tb[row][col + 1] = target_tb[row][col + 1] + 1
	target_tb[row][col + 2] = target_tb[row][col + 2] + 1
end

-- hint_number를 기록한 hint_table을 만든다.
function regist_hintnumber_to_hinttable( source_tb, target_tb, row, col )
	local iii = 1
	while iii <= row do
		local jjj = 1
		while jjj <= col do
			if "*" == source_tb[iii][ jjj ] then
				regist_hintnumber_to_hinttable_impl( target_tb, iii, jjj )
			end
			jjj = jjj + 1
		end
		iii = iii + 1
	end
end

-- 마인을 표시해 준다.
function regist_mine_to_hinttable( source_tb, target_tb, row, col )

local iii = 1
	while iii <= row do

local jjj = 1
		while jjj <= col do
			if "*" == source_tb[iii][ jjj ] then
				target_tb[iii][jjj] = "*"
			end

jjj = jjj + 1
		end
		iii = iii + 1
	end
end

-- hint_table 을 원래 크기로 만든다.
function resize_hinttable( target_tb )
	local iii = 1
	while iii <= #target_tb do
		table.remove( target_tb[iii], #target_tb[iii] ) -- 끝 삭제
		table.remove( target_tb[iii], 1 ) -- 앞 삭제
		iii = iii + 1
	end

table.remove( target_tb, #target_tb )
	table.remove( target_tb, 1 )
end

function get_hint_table( tb, row, col )
	local hint_table = create_hinttable( row, col )

-- hint_table에 hint_number를 source_tb 에서 추출하여 기록한다.
	regist_hintnumber_to_hinttable( tb, hint_table, row, col )

-- hint_table 을 원래 크기로 만든다.
	resize_hinttable( hint_table )

-- 마인을 표시해 준다.
	regist_mine_to_hinttable( tb, hint_table, row, col )

return hint_table

end

-- 탐지된 마인 뿌리기
function print_hint_table( target_tb )
	local iii = 1

while iii <= #target_tb do
		local jjj = 1

local temp_string = ""
		while jjj <= #target_tb[iii] do
			temp_string = temp_string .. target_tb[iii][ jjj ]
			jjj = jjj + 1
		end
		print( temp_string )
		iii = iii + 1
	end
end

function main()
	-- 진행 카운트
	local loop_count = 1

while true do

-- 행 열 입력
		local row, col = io.read( "*number", "*number", 1 )

-- 정상종료 인지 체크
		if true == ( 0 == row and 0 == col ) then
			return "정상 종료"
		end

-- 종료가 아니라면 진행
		local minefield_table = create_minefield_table( row )

-- 한줄 단위로 마인을 심는다.
		local i = 1
		while i <= row do
			s = io.read( col )
			print()

ret = regist_mine_to_minefield_table( minefield_table[i], s, col )
			if false == ret then
				return "칸을 맞추지 못했거나, '*' 나 '.' 문자를 사용하지 않았습니다"
			end

i = i + 1
		end

-- 힌트 테이블 만들기
		local hint_table = get_hint_table( minefield_table, row, col )

-- 탐지된 마인 뿌리기
		print( "#Field No. ".. loop_count )
		print_hint_table( hint_table )

-- 카운트 증가
		loop_count = loop_count + 1
	end
end

print( main() )
-- 기본 적인 알고리즘
-- 지뢰를 심어 놓은 테이블을 준비 한다. 이하 source_table
-- 지뢰를 심어 놓은 테이블 보다 row + 2, col + 2 만큼 큰 테이블을 준비한다. 이하 hint_table

-- hint_table 의 모든 원소 값을 0 으로 초기화 한다.
-- source_table에 있는 지뢰의 위치를 row, col 로 뺀다.

-- hint_table의 row, col 에 1씩 더한다. 이 작업은 row + 2, col + 2 까지 한다.
-- hint_table 의 양쪽 열 과, 상하 행을 모두 지운다.

-- 다시 source_table 에 있는 지뢰의 위치를 row, col 로 뺀다.
-- hint_table 에 row,col 에 위치한 값을 지뢰로 바꾼다.

-- 그러면, 지뢰를 찾기 위한 hint_table 이 완성 된다.

저작자표시

'책 정리 > Programming Challenges : 알고리즘 트래이닝 북' 카테고리의 다른 글

문제 10, 포커 패 (Poker Hands) (1)	2009.11.06
문제 9, 유쾌한 점퍼 (Jully Jumpers) (2)	2009.11.01
문제 8, 호주식 투표법 (Australian Voting) (1)	2009.11.01
문제 7 : 체크 확인 - Check the Check (4)	2009.10.28
문제 6 : 인터프리터(Interpreter) (2)	2009.10.22
문제 5 : 그래픽 편집기(Graphical Editor) (1)	2009.10.13
문제 4 : LCD 디스플레이(LCD Display) (3)	2009.03.01
문제 3 : 여행 ( The Trip ) (1)	2009.02.19
문제 1 : 3n + 1 문제 ( The 3n+1 Problem ) (0)	2009.02.15
알고리즘 트레이닝 북 (PROGRAMMING CHALLENGES) (0)	2009.02.15