[platinum3] [풀이, 분류 미확인] boj2873 롤러코스터

 

오랜만에 높은 티어의 문제를 풀었다. 요샌 골드1~3 문제들만 풀고 있는데, 시간 줄이는게 너무 어렵다.. 낯선 문제들은 아이디어 떠올리는데도 최소 20분 이상 걸린다. 양치기로 수많은 문제들에 익숙해지는 거 외에는 방법이 없을 것 같다.

 

이 문제는 관찰과 구현 방식이 중요한 문제로, 옛날 고난도 문제 풀때 노가다의 고통을 다시 상기시킬 수 있었던 문제이다.

 

key idea : 

  행 ,열 중 하나라도 칸수가 홀수라면 무조건 모든 칸 방문 가능하다. (이건 금방 어렵지 않게 떠올 릴 수 있다.)

 행,열 모두 짝수라면,,, 어떻게 될까?

 관찰을 통해 다음과 같이 알 수 있었다.

관찰 결과, 다음과 같이  한칸을 제외하곤 모두 방문이 가능한 칸들이 있다.

제외할 한 칸이 (r, c) 일때

 r== 짝수 && c == 홀수  or   r== 홀수 && c == 홀수  일때 가능하다. (여기까지는 금방 발견할 수 있다.).

아래 초록 점이 찍힌 칸들은 모두 제외 가능한 칸들이다.

 

 

 

그렇다면 당연히 이 한칸을 제외한 모든 칸을 방문할 수 있으니, 초록 칸들 중 가장 작은 값을 제외한 경로가 답이 될 것이다.

 

이제 본격적인 문제는 이걸 어떻게 구현할 것이냐 이다.

 

나같은 경우는 다음과 같이 구현하였다.

 

 

  제외할 칸(rx, ry)   rx == 홀수 ry== 짝수일때

 

1.시작점부터 아래와 같이 방문한다. (좌우 지그재그)  제외할 칸 맨위까지 ry = 0 까지 채운다.

 

2. 1 ~ ry  칸수는 짝수가 될 것이다. 다음과 같이 (rx + 1 , ry ) 까지 상하 지그재그로 방문한다.

3. 다음 구현이 까다로웠는데,  ( ry + (rx + 1 ~ R 까지 칸의 갯수)  , R )까지 다음과 같이 방문한다. (어떤 방식으로 방문하는지는 추후 서술)

4. 마지막은 상하 지그재그로 마무리

  제외할 칸(rx, ry)   rx == 짝수  ry== 홀수일때

 

 1. 왼쪽 부터 상하 지그재그로 채운다.

       2. 위쪽부터 아래로 좌우 지그재그로 채운다. ( rx, ry + 1)까지

3.   아까와 같이  ( ry + (rx + 1 ~ R 까지 칸의 갯수)  , R )까지 다음과 같이 방문한다. (어떤 방식으로 방문하는지는 추후 서술)

 

4.마지막은 아까와 같이 상하 지그재그로 마무리

 

 

위와 같이 간략화 할 수 있는게 나의 최선이였다. 

파란색, 연파란색은 각각 다른 타입의 길 찾기 알고리즘 이다.

관찰 결과 좌우 지그재그 (파랑색)과 3번의 알고리즘은 같은 타입으로 퉁칠 수 있었다.

 

 

타입1. 

 순서대로 1번쪽으로 갈려할 때  

     경계값(R,C)를 벗어나거나

     이미 방문했거나

     갈려는 곳이 제외하는 칸(rx, ry)

일 경우 2번, 2번도 마찬가지면 3번... 식으로 간다.

 

위와 같이 고안한 이유는  왼쪽위에서 오른쪽 아래로 내려갈 때 모든 칸을 방문하려면(rx,ry 제외) 방문안한 칸은 무조건 채우러 가야하기 때문에 미쳐 못채운 것은 채워야 하기 때문에  U(위) , L(왼쪽)으로 가는 것을 최우선으로 두었다.

 

위의 알고리즘대로 탐색할 경우 다음과 같이 작동한다.

 

(아무 방해물이 없을 경우)  좌우 지그재그로 내려간다.

(아무 방해물이 없을 경우)  좌우 지그재그로 내려간다.

 

(방해물 (rx, ry) 가 있을 경우)

다음과 같이 왼쪽 위 에서 오른쪽 아래로 꽉꽉 채워 방문하며 내려간다.

 

 

처음에는 위의 알고리즘으로 모두 방문할 줄 알았지만 예외의 경우가 있었다.

다음과 같이 방문 후 남는 부분은 상하 지그재그로 마무리 해야 한다. 즉 두번째 알고리즘(연파랑색)은  꽉꽉 채워 내려갈 용도보다는 예외가 발생할 경우(상하 지그재그가 필요할 때만)사용하는 목적이다.

작성한 답안에는 왼쪽부분 까지 구현했지만, 지금보니 그럴 필요가 없었다..

 

 

 

 

 

 

또한 예외 상황들도 있다. 

 

 

 

 

다음과 같이 제외 대상이 맨 오른쪽에 있는경우,   2번째 단계  상하 지그재그는 (rx + 1 , ry ) 가 아닌 (rx , ry - 1 )까지 진행하고 나머지는 좌우 지그재그로 마무리.

 

 

 

다음과 같이 제외대상이 맨 아래에 있는 경우,  좌우 지그재그를 (rx, ry + 1)까지가 아낸 (rx  - 1 , ry)까지 하고 상하 지그재그로 마무리.

이렇게 예외케이스 까지 고려해 풀면 구현이 마무리된다. 아직 안 찾아봤지만 왠지 더 간단한 방법이 있을 것 같은 느낌이 들지만... 보다시피 구현이 쉽지 않았다. 그래도 2종류의 길찾기 알고리즘으로 모든 케이스들을 퉁칠 수 있어서 생각보다 구현이 길지는 않았다.

 이문제 푸는데 시간을 너무 많이 낭비해서... 이제 당분간 플레 상위 구간은 건들지 말아야겠다.