문제 18, 월도르프를 찾아라, Where's Waldorf? PC/UVa ID : 110302/10010

PC/UVa ID : 110302/10010

이 포스트를 만든 목적

• 생각 절차, 푼 방법, 고민거리 등을 기록하기 위해서 만들었다.
  

이 포스트의 준비물

• firefox4 b8
  
• eclipse 3.6.1 + vrapper
  
• lua 5.1.4
  
• windows snapshot maker
  

참조 문헌

• 스티븐 스키에나, 미구엘 레비야 저. Programming Challenges: 알고리즘 트레이닝 북. 서환수 역.
  Springer. 한빛미디어 초판 2쇄 2004.12.05. (문제 18, 월도르프를 찾아라, page 97 ~ 98)
  

참고 링크

• http://www.lua.org/manual/5.1/manual.html  - 루아 메뉴얼, 스트링 찾을려고
  
• http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=12&page=show_problem&problem=951 - 원문 참조
  

문제

1. 문자들로 이루어진 그리드(grid)에서 지정한 단어를 찾고, 그 찾은 위치를 출력하라.
   
   
2. 프로그램은 첫번째로 케이스 갯수를 양의 정수로 입력 받는다.
   - 이 케이스 수 만큼 새로운 월도르프를 찾을 것이다.
   
3. 케이스 갯수를 입력 받았으면, 한줄 띄운다.
   
   
4. 그리드의 row, col를 양의 정수로 입력 받는다.
   - 이때 1 <= row, col <= 50 의 제한을 갖는다.
   
   
5. 그리드의 크기 입력이 끝났으면, 문자열 그리드를 입력 받는다.
   - 이때 문자열 길이는  col, 문자열 갯수는 row 만큼 정확히 받아야 한다.
   
   
6. 5번이 끝나면, 그리드 속에서 찾을 단어의 갯수를 양의 정수로 입력 받는다.
   
7. 6번이 끝나면, 찾을 단어 만큼 입력 받는다.
   
   
8. 7번까지 끝나면, 프로그램을 그리드 속에서 지정한 단어를 찾는데, 찾는 방법은 다음과 같다.
   - 현재 위치의 상하좌우 4방향, 대각선 4방향, 이렇게 8방향
   
   
9. 단어를 찾았다면, 단어의 첫 시작 위치를 출력해 줘야 한다.
   
   
10. 모든 단어를 다 찾았다면, 다시 4번부터 시작하여, 모든 케이스가 끝날 때까지 반복한다.
    
    
11. 자세한 사항은 첨부한 그림에서, 입출력을 보고, 더 나아가 참조한 원문 링크를 따라가길 바란다.
    

출력 예외 상황

• 한 단어가 그리드에서 두번 이상 반복 된다면, 그리드의 좌측 상단에서 제일 가까운 위치를 출력한다.
  - C의 배열 관점에선 0, 0 이다.
  - 루아의 테이블 관점에선 1, 1 이다.
  

맛보기 코드 - 본 코드는 루아로 작성 되었으며, 실행 하려면, 루아 인터프리터가 필요하다.
-- Where's Waldorf -- PC/UVa : 110302/10010 -- http://ikpil.com -- 2010.12.30 -- input for case count function fn_input_case_count() local case_count = io.read("*number") print() io.flush() return case_count end -- input for grid size function fn_input_grid_size() -- grid row, col return io.read("*number", "*number") end -- input for table grid by string grid function fn_input_grid(row, col) local tb_grid = {} local row_count = 1 while row_count <= row do local str_grid = io.read("*line") str_grid = string.upper(str_grid) if col == string.len(str_grid) then local tb_grid_col = {} for w in string.gmatch(str_grid, "%a") do tb_grid_col[#tb_grid_col + 1] = w end tb_grid[row_count] = tb_grid_col row_count = row_count + 1 end end return tb_grid end -- input for waldorfs function fn_input_waldorfs() local waldorf_count = io.read("*number") local tb_waldorfs = {} local i = 1 while i <= waldorf_count do local str_waldorf = io.read("*line") if nil ~= str_waldorf and "" ~= str_waldorf then str_waldorf = string.upper(str_waldorf) local tb_waldorf = {} for w in string.gmatch(str_waldorf, "%a") do tb_waldorf[#tb_waldorf + 1] = w end tb_waldorfs[#tb_waldorfs + 1] = tb_waldorf i = i + 1 end end return tb_waldorfs end function fn_where_is_real(tb_arg, tb_dir, tb_waldorf) -- for simple name local tb_grid, tb_result = tb_arg.tb_grid, tb_arg.tb_result local x, y, w, h, cur = tb_arg.x, tb_arg.y, #tb_grid[1], #tb_grid, 1 while 1 <= x and x <= w and 1 <= y and y <= h and -- for scope 0 ~= #tb_waldorf and tb_grid[y][x] == tb_waldorf[cur] -- for waldorf do if cur == #tb_waldorf then return true end x, y, cur = x + tb_dir.x, y + tb_dir.y, cur + 1 end return false end -- where is waldorf? function fn_where_is(tb_arg) -- waldorf seqence loop, direction loop for k, tb_waldorf in pairs(tb_arg.tb_waldorfs) do for k, tb_dir in pairs(tb_arg.tb_directions) do -- for debug -- print(string.format("search waldorf:%s dir x:%d, y:%d", -- table.concat(tb_waldorf), tb_dir.x, tb_dir.y)) -- io.flush() if true == fn_where_is_real(tb_arg, tb_dir, tb_waldorf) then return true end end end return false end function main() local tb_directions ={{x=-1, y=-1}, {x=0, y=-1}, {x=1, y=-1}, {x=-1, y= 0}, {x=1, y= 0}, {x=-1, y= 1}, {x=0, y= 1}, {x=1, y= 1}} -- input value local case_count = fn_input_case_count() for i = 1, case_count, 1 do local grid_row, grid_col = fn_input_grid_size() local tb_grid = fn_input_grid(grid_row, grid_col) local tb_waldorfs = fn_input_waldorfs() -- make arg local tb_arg = {} tb_arg.tb_grid = tb_grid tb_arg.tb_waldorfs = tb_waldorfs tb_arg.tb_directions = tb_directions -- logic for row = 1, #tb_grid, 1 do for col = 1, #tb_grid[row], 1 do --print(string.format("grid x:%d, y:%d", row, col)) --io.flush() tb_arg.x, tb_arg.y = col, row if true == fn_where_is(tb_arg) then print(row, col) end end end end end main()

여담

• lua에선 스트링 접근이 쉽지 않아, 테이블로 만들어 버렸다.
  - 그리드 입력 받을 때, 월도르프 입력 받을 때, 변환 작업을 시켰다.
  
  
• 이 문제는 방향을 변수로 인식하는게 핵심이다. 방향을 변수화 시키면, 하나의 while 문으로 8 방향 모두 다 검색 가능하며 더 나아가 방향성이 더 다양하게 되더라도, 문제없이(물론 범위 내에서만 ;) ) 탐색이 가능해 진다.
  - 변수화 시킨 방법은 맛보기 코드에서 참조하라
  
  
• 구현에 있어 어려운건 없었으나, 디버깅이 필요한 시점에 Break Point 를 걸수 없어, 노가다 print 문을 했었다는게 좀 찔린다.
  - eclipse 에서도 루아 디버깅 모드가 있다고 하니, 찾아서 적용 시켜 봐야 겠다.
  
  
• 루아에선 for 문은 완전히 범위로 루프를 돌릴 때 사용하고, while 은 상태로 루프를 돌릴 때 사용 하는 것으로 굳혔다고 본다.
  

:wq