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)

참고 링크

문제

  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 이다.

맛보기 코드 - 본 코드는 루아로 작성 되었으며, 실행 하려면, 루아 인터프리터가 필요하다.

여담

  • lua에선 스트링 접근이 쉽지 않아, 테이블로 만들어 버렸다.
    - 그리드 입력 받을 때, 월도르프 입력 받을 때, 변환 작업을 시켰다.

  • 이 문제는 방향을 변수로 인식하는게 핵심이다. 방향을 변수화 시키면, 하나의 while 문으로 8 방향 모두 다 검색 가능하며 더 나아가 방향성이 더 다양하게 되더라도, 문제없이(물론 범위 내에서만 ;) ) 탐색이 가능해 진다.
    - 변수화 시킨 방법은 맛보기 코드에서 참조하라

  • 구현에 있어 어려운건 없었으나, 디버깅이 필요한 시점에 Break Point 를 걸수 없어, 노가다 print 문을 했었다는게 좀 찔린다.
    - eclipse 에서도 루아 디버깅 모드가 있다고 하니, 찾아서 적용 시켜 봐야 겠다.

  • 루아에선 for 문은 완전히 범위로 루프를 돌릴 때 사용하고, while 은 상태로 루프를 돌릴 때 사용 하는 것으로 굳혔다고 본다.

:wq

posted by 농사를 짓는 게임 프로그래머 최익필

댓글을 달아 주세요