[ 백준 ] 10252 / 그리드 그래프

15051 단어 psbojboj

# Appreciation

/*
 * Problem :: 10252 / 그리드 그래프
 *
 * Kind :: Simulation
 *
 * Insight
 * - DFS 로 구하려했다가... 시간초과
 *   + 그럼 도대체 어떻게 구하지?
 *     # 그렇게 해밀턴 회로를 구하기 위해 끄적끄적 거리던 중
 *       M,N 이 짝수이면 무조건 가능한 경우를 발견했다
 *       -> 3x4
 *          s --- -
 *          | | | |
 *          --- ---
 *
 *       -> 4x3
 *          s-------
 *                 |
 *          --------
 *          |
 *          --------
 *                 |
 *          --------
 *
 *       -> 3x3
 *          s---- -
 *              | |
 *          ----- |
 *          |     |
 *          -------
 *
 * Point
 * - 그냥 구하면 되는 거였구나...
 *   + 그동안 가지고 있던 알고리즘 문제에 대한 선입견을 깨주는 문제다
 */

# Code

//
//  BOJ
//  ver.C++
//
//  Created by GGlifer
//
//  Open Source

#include <iostream>
#include <vector>

using namespace std;

#define endl '\n'

// Set up : Global Variables
struct Point { int y, x; };

// Set up : Functions Declaration
/* None */


int main()
{
    // Set up : I/O
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // Set up : Input
    int T; cin >> T;

    while (T--) {
        int M, N;
        cin >> M >> N;

        // Process
        vector<Point> P;
        /* DA - 아래로 A칸
         * UB - 위로 B칸
         * LC - 왼쪽으로 C칸
         * RD - 오른쪽으로 D칸 */
        if (M%2 == 0) { /* DM, R1, UM, R1, DM, R1, UM, R1, ... */
            for (int i=0; i<M; i+=2) {
                for (int j=0; j<N; j++)
                    P.push_back({i, j});
                for (int j=N-1; j>=0; j--)
                    P.push_back({i+1, j});
            }
        } else if (N%2 == 0) { /* RN, D1, LN, D1, RN, D1, LN, D1, ... */
            for (int j=0; j<N; j+=2) {
                for (int i=0; i<M; i++)
                    P.push_back({i, j});
                for (int i=M-1; i>=0; i--)
                    P.push_back({i, j+1});
            }
        } else { /* R(N-1), D1, L(N-1), D1, ..., RN, U(M-1) */
            for (int i=0; i<M-1; i+=2) {
                for (int j=0; j<N-1; j++)
                    P.push_back({i, j});
                for (int j=N-2; j>=0; j--)
                    P.push_back({i+1, j});
            } for (int j=0; j<N-1; j++) {
                P.push_back({M-1, j});
            } for (int i=M-1; i>=0; i--) {
                P.push_back({i, N-1});
            }
        }

        // Control : Output
        cout << 1 << endl;
        for (Point p : P) {
            cout << "(" << p.y << "," << p.x << ")" << endl;
        }
    }
}

// Helper Functions
/* None */

좋은 웹페이지 즐겨찾기