[ 백준 ] 10252 / 그리드 그래프
# 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 */
Author And Source
이 문제에 관하여([ 백준 ] 10252 / 그리드 그래프), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@gglifer/백준-10252-그리드-그래프
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
/*
* Problem :: 10252 / 그리드 그래프
*
* Kind :: Simulation
*
* Insight
* - DFS 로 구하려했다가... 시간초과
* + 그럼 도대체 어떻게 구하지?
* # 그렇게 해밀턴 회로를 구하기 위해 끄적끄적 거리던 중
* M,N 이 짝수이면 무조건 가능한 경우를 발견했다
* -> 3x4
* s --- -
* | | | |
* --- ---
*
* -> 4x3
* s-------
* |
* --------
* |
* --------
* |
* --------
*
* -> 3x3
* s---- -
* | |
* ----- |
* | |
* -------
*
* Point
* - 그냥 구하면 되는 거였구나...
* + 그동안 가지고 있던 알고리즘 문제에 대한 선입견을 깨주는 문제다
*/
//
// 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 */
Author And Source
이 문제에 관하여([ 백준 ] 10252 / 그리드 그래프), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@gglifer/백준-10252-그리드-그래프저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)