올해 대회 아닙니다. 옛날 대회입니다. 낚이신분들 ㅈㅅ ㅋ
난데없는 2005년도 대회 공략
springnote에서 작성한 글을 바로 복붙
TJU에서 채점을 해주니 관심있으신 분들은 풀이 안보고 한번 풀어보시는 건 어떨까요?
개요

• 걸린 시간 : 1.5시간
  
• 제출 횟수 : 1회
  
• 문제 링크 : 2005g.pdf
  
• 문제 풀이 : G.cpp
  

• Cannon이 이동할 수 있는 범위는 크게 네개이다.
  
  • 오른쪽에 있는 말을 뛰어넘어서 바로 다음 위치에 내려앉는다(F가 막고있지 않는 한)
  • 오른쪽에 있는 말을 뛰어넘어서 빈칸들을 무시하고 다음 말을 잡아먹는 위치로 이동한다.
  • 왼쪽으로도 마찬가지
    
• 즉, CFBBBE... 형태의 배치에서 C가 이동할 수 있는 범위는
  <ul><li>F를 넘어 B에,</li><li>아니면 BBB를 건너 E를 잡아먹는 위치</li><li>둘 중 하나만 선택하면 된다는 것이다.</li></ul>
• 처음엔 이걸 가지고 4방향 BFS를 돌리면 될 거라고 생각해서 구현했다.
• 그러나 최악의 경우 상당히 많은 이동 횟수가 필요하기 때문에, 몇몇 critical한 데이터에서 TLE가 발생했다.

풀이 - Second

• 실제 말이 이동하는 BFS 상태공간을 텍스트로 몇개 찍어보자, 다소 쓸데없는 move를 확인할 수 있었다.
  
  • K가 있지 않은 반대 방향의 말을 (!많이!) 잡아먹을 이유가 없다.
    
    • K 반대 방향으로 이동해봤자, 결국은 다시 K 방향으로 이동해야 할 텐데 이런 move가 유효한 것은
      
      • K 방향에 있는 첫번째 E 혹은 K를 잡아먹는 경우 (예제 : BFCEEK의 경우, 왼쪽의 B 이후 오른쪽으로 이동해서 E를 잡고 다시 K를 잡는게 최소의 move이다)
    • 외에는 없기 때문이다. (정확한 증명은 귀류법을 이용하면 가능하다. K반대로 이동해서 여러번 이동한 다음 다시 K방향으로 이동하는 최단경로가 있다고 가정하자, ... , 모순이다)
    • 그
      러므로 위의 개선사항을 반영하기 위해, C의 현재 위치에서 K 반대 방향으로 이동할 수 있는지/없는지 여부만 저장하고 실제 K
      반대방향의 board 정보는 지워버리고, 한번 방문한 상태정보는 다시 방문하지 않도록 BFS를 돌렸다.
    • Accepted
    [이 글은 과거 홈페이지에서 이전된 글입니다. 원문보기]
    
    14년 전