백준 2873 롤러코스터

2873번: 롤러코스터

이 문제는 조금 까다로운 구현 문제다. 노트에 행과 열이 (홀, 홀), (홀, 짝), (짝, 홀), (짝, 짝)일 때 각각 그려보면 쉽게 아이디어를 얻을 수 있다.

1. 행과 열 중 홀수가 존재할 때 - 모든 수를 지날 수 있다
2. 행과 열이 모두 짝수일 때 - 1개 이상의 점을 지날 수 없다
   행이 i, 열이 j일 때 i+j가 짝수인 점은 무조건 지나게 된다. (기쁨이 제일 작더라도 제외할 수 없다)
   따라서, i+j가 홀수인 점 중 가장 기쁨이 작은 점을 제외하고 지나는 경로를 출력하는 것이 이 문제의 답이다.

i+j가 홀수이면 i혹은 j가 홀수라는 뜻인데, 처음에는 각각에 맞는 함수를 구현하려고 했지만 한개의 함수안에서 if문으로 쉽게 해결할 수 있었다.

1. 행이나 열이 홀수일 때는 'ㄹ'모양으로 모든 점을 지날 수 있다.
2. 행과 열이 모두 짝수일 때는 먼저 i+j가 홀수인 점의 i, j를 저장한다.
   'ㄷ'의 반대 모양으로 열에서 두 칸씩 내려오다가 저장한 행이 존재하는 두 칸을 만나면 'ㅂ'자로 이동하는 것을 반복한다.
   이 또한 행에서 두 칸씩 이동하고, 점이 존재하는 두 칸을 만나면 왼쪽 아래 지점, 오른쪽 위에 점에 따라 "RD", "DR"을 출력한다. flag로 점을 지났음을 기록하고, 이후에는 'ㄹ'의 반대 방향으로 내려온다.

 #include<bits/stdc++.h>
 using namespace std;
 int board[1001][1001], r, c, Min = 1e9, Min_r, Min_c;
 void odd()
 {
     if(r%2 == 1)
     {
         bool flag = false;
         for(int i=0; i<r; i++)
         {
             for(int j=0; j+1<c; j++)
             {
                 if(!flag) cout << 'R';
                 else cout << 'L';
             }
             flag = 1 - flag;
             if(i+1 < r) cout << 'D';
         }
     }
     else
     {
         bool flag = false;
         for(int i=0; i<c; i++)
         {
             for(int j=0; j+1<r; j++)
             {
                 if(!flag) cout << 'D';
                 else cout << 'U';
             }
             flag = 1 - flag;
             if(i+1 < c) cout << 'R';
         }
     }
 }
 void even()
 {
     bool flag = false;
     int cur_r = 0, cur_c = 0;
     while(cur_r < r)
     {
         if(cur_r == Min_r || cur_r+1 == Min_r)
         {
             bool pass = false;
             while(cur_c < c)
             {
                 if(Min_c == cur_c)
                 {
                     pass = true;
                     cout << "RD";
                 }
                 else if(Min_c == cur_c + 1)
                 {
                     pass = true;
                     cout << "DR";
                 }
                 else if(!pass) cout << "DRUR";
                 else cout << "RURD";
                 cur_c += 2;
             }
             if(cur_r + 2 == r) return;
             cout << 'D';
             flag = true;
         }
         else if(!flag)
         {
             for(int i=0; i+1<c; i++) cout << 'R';
             cout << 'D';
             for(int i=0; i+1<c; i++) cout << 'L';
             cout << 'D';
         }
         else
         {
             for(int i=0; i+1<c; i++) cout << 'L';
             cout << 'D';
             for(int i=0; i+1<c; i++) cout << 'R';
             if(cur_r + 2 == r) return;
             cout << 'D';
         }
         cur_r += 2;
     }
 }
 void solve()
 {
     if(r%2 == 1 || c%2 == 1) odd();
     else even();
 }
 int main()
 {
     cin >> r >> c;
     for(int i=0; i<r; i++)
     {
         for(int j=0; j<c; j++)
         {
             cin >> board[i][j];
             if((i+j) %2 == 1 && board[i][j] < Min)
             {
                 Min_r = i, Min_c = j;
                 Min = board[i][j];
             }
         }
     }
     solve();
 }