Infinity Area (8pts)
Problem
Kick Start - Google’s Coding Competitions
Hone your coding skills with algorithmic puzzles meant for students and those new to coding competitions. Participate in one round or join them all.
codingcompetitions.withgoogle.com
문제의 단순성을 위해 무한대라는 기호가 아래와 같이 원들이 외부에서 만나는 점 S라고 가정하고, 이를 무한대의 중심이라고 부르자.
세 정수 R, A, B가 주어진다. 너는 지금 무한대의 중심에 있다. 먼저 반지름이 R인 원을 오른쪽에 그리고 다시 무한대의 중심으로 돌아온다. 다음으로 이전 반지름에 A를 곱한 것과 동일한 반지름인 원을 왼쪽에 그린다. 다시 무한대의 중심에 돌아오면 이전 반지름에 B를 나눈(정수 나눗셈) 것과 동일한 반지름인 원을 오른쪽에 그린다. 다시 무한대의 중심에 돌아오면 이전 반지름에 A를 곱한 것과 동일한 반지름인 원을 왼쪽에 그린다.
너는 반지름이 0이 될 때까지 위와 같이 왼쪽과 오른쪽에 원을 그려나간다. 그려진 모든 원들의 넓이 합을 계산하여라. 유한 횟수 안에 작업이 끝난다는 것이 보장된다.
Input
입력의 첫 번째 줄에는 테스트 케이스의 수, T가 주어진다. T개의 줄이 이어진다.
각 줄은 테스트 케이스를 나타내며, 세 정수 R, A, B로 이루어져 있다. R은 첫 원의 반지름을 나타내고, A와 B는 그다음 원들의 반지름을 구하는 데 사용되는 파라미터이다.
Output
각각의 테스트 케이스에 대하여, Case #x: y를 포함하는 하나의 줄을 출력하여라. x는 테스트 케이스 번호(1부터 시작)이며, y는 그려지는 반지름이 0이 될 때까지 그려진 모든 원들의 넓이 합이다.
Limits
시간 제한: 20초
메모리 제한: 1GB
Test Set 1
$1 \le T \le 100$
$1 \le R \le 10^5$
$1 \le A \le 500$
$2 \times A \le B \le 1000$
Sample
| Sample Input | Sampel Output |
| 2 1 3 6 5 2 5 |
Case #1: 31.415927 Case #2: 455.530935 |
Sample Case #1에서, 반지름이 1인 원을 오른쪽에 그린다. 무한대의 중심에 도착하면 반지름이 $1 \times 3 = 3$인 원을 왼쪽에 그린다. 다시 무한대의 중심에 도착하면 반지름이 $\lfloor 3/6 \rfloor = 0$이기 때문에 오른쪽 원을 그리는 것을 멈춘다. 그려진 원들의 넓이 합은 $\pi \times 1 \times 1 + \pi \times 3 \times 3 \approx 31.415927$이다.
Sample Case #2에서, 반지름이 5인 원을 오른쪽에 그린다. 무한대의 중심에 도착하면 반지름이 $5 \times 2 = 10$인 원을 왼쪽에 그린다. 무한대의 중심에 도착하면 반지름이 $\lfloor 10/5 \rfloor = 2$인 원을 오른쪽에 그린다. 무한대의 중심에 도착하면 반지름이 $2 \times 2 = 4$인 원을 왼쪽에 그린다. 무한대의 중심에 도착하면 다음 원의 반지름이 $\lfloor 4/5 \rfloor = 0$이기 때문에 그리는 것을 멈춘다. 그러므로 그려진 원들의 넓이의 합은 $\pi \times 5 \times 5 + \pi \times 10 \times 10 + \pi \times 2 \times 2 + \pi \times 4 \times 4 \approx 455.530935$이다.
Tutorial
단순 구현 문제이다. 초기 반지름이 최대 $10^5$이고, $A < B$이기 때문에 오른쪽과 왼쪽 원을 그리고 나면 반지름은 최소 1씩은 작아지게 된다. 즉, 반지름이 0이 될 때까지 직접 구해도 제한 시간 안에 답을 구할 수 있다는 뜻이다(사실 이렇게 말고 할 수 있는 방법도 없다).
Solution
#include <bits/stdc++.h>
using namespace std;
int main()
{
int T, C, r, a, b;
double sum;
cout << setprecision(16);
cin >> T;
for(C=1; C<=T; C++){
cin >> r >> a >> b;
sum = 0;
while(r){
sum += M_PI * r*r;
sum += M_PI * r*r*a*a;
r = r * a / b;
}
cout << "Case #" << C << ": ";
cout << sum << '\n';
}
return 0;
}
B. Palindromic Factors (6pts, 9pts)
Problem
Palindromic Factors (6pts, 9pts)
Kick Start - Google’s Coding Competitions
Hone your coding skills with algorithmic puzzles meant for students and those new to coding competitions. Participate in one round or join them all.
codingcompetitions.withgoogle.com
양의 정수 A가 주어진다. 회문인 A의 약수 개수를 구하여라. 뒤집어도 같은 숫자를 회문이라고 부른다. 예를 들어, 121은 회문이지만, 123은 아니다.
Input
입력의 첫째 줄에는 테스트 케이스, T가 주어진다. T개의 줄이 이어진다.
각 줄은 테스트 케이스를 나타내며, 하나의 정수 A가 포함된다.
Output
각 테스트 케이스에 대하여, Case #x: y를 포함하는 하나의 줄을 출력하여라. x는 테스트 케이스의 번호(1번부터 시작)이며, y는 회문인 A의 약수 개수이다.
Limits
시간 제한: 2초.
메모리 제한: 1GB.
$1 \le T \le 100$.
Test Set 1
$1 \le A \le 10^3$
Test Set 2
$1 \le A \le 10^{10}$
Sample
| Sample Input | Sample Output |
| 4 6 10 144 242 |
Case #1: 4 Case #2: 3 Case #3: 7 Case #4: 6 |
첫 번째 테스트 케이스에서, A는 4개의 회문인 약수를 가진다: 1, 2, 3, 6
두 번째 테스트 케이스에서, A는 3개의 회문인 약수를 가진다: 1, 2, 5
세 번째 테스트 케이스에서, A는 7개의 회문인 약수를 가진다: 1, 2, 3, 4, 6, 8, 9
네 번째 테스트 케이스에서, A는 6개의 회문인 약수를 가진다: 1, 2, 11, 22, 121, 242
Tutorial
약수와 관련된 문제를 푸신 분들은 쉽게 풀 수 있을 것이다. 결론을 먼저 말하면 $O(\sqrt{A})$에 해결이 가능하다.
우선 회문인지를 판단하는 것은 그리 어렵지 않다. 각 자리를 분리한 후, 앞과 뒤에서 동시에 읽으면서 같은지를 확인해주면 된다. 그렇다면 약수를 구하는 것이 문제인데, 이는 $x$가 A의 약수이면 ${A \over x}$도 A의 약수라는 성질을 이용해 1부터 $\sqrt{A}$까지만 반복문을 돌려 A의 약수를 구해주면 된다. $x^2 = A$일 때, $x$를 2번($x$와 ${A \over x}$) 세지 않도록 주의하자(내가 그래서 제출 횟수를 한번 날렸다 ㅜㅜ).
Solution
#include <bits/stdc++.h>
using namespace std;
bool is_palindrome(long long x);
int main()
{
int T, C, cnt;
long long i, a;
cin >> T;
for(C=1; C<=T; C++){
cin >> a;
cnt = 0;
for(i=1; i*i<=a; i++){
if(a%i == 0){
if(is_palindrome(i)) cnt++;
if(i != a/i && is_palindrome(a/i)) cnt++;
}
}
cout << "Case #" << C << ": ";
cout << cnt << '\n';
}
return 0;
}
bool is_palindrome(long long x)
{
int i;
vector<int> arr;
while(x){
arr.push_back(x%10);
x /= 10;
}
for(i=0; i<arr.size(); i++){
if(arr[i] != arr[arr.size()-i-1]) return false;
}
return true;
}
Unlock the Padlock (10pts, 11pts, 14pts)
Problem
Unlock the Padlock (10pts, 11pts, 14pts)
Kick Start - Google’s Coding Competitions
Hone your coding skills with algorithmic puzzles meant for students and those new to coding competitions. Participate in one round or join them all.
codingcompetitions.withgoogle.com
처음에 임의의 조합으로 설정된 N개의 다이얼로 이루어진 자물쇠가 있다고 생각해보자. 자물쇠의 다이얼 크기는 D이다. 이는 다이얼이 0부터 D-1까지의 값을 가지는 것을 의미하며, 이는 위 혹은 아래로 돌릴 수 있다. 다이얼들은 왼쪽에서 오른쪽으로 번호가 있으며, 가장 왼쪽이 1, 가장 오른쪽이 N이다. 자물쇠는 모든 다이얼의 값을 0으로 만들면 열 수 있다.
너는 0번 이상 다음의 작업을 할 수 있다:
- $1 \le l \le r \le N$인 범위 [l, r]을 고르고 [l, r]의 모든 다이얼을 위 혹은 아래로 같이 돌린다. 위로 돌리면 [l, r] 범위의 다이얼들의 값 1 증가하고, 아래로 돌리면 값이 1 감소한다. 값이 D-1인 다이얼은 증가하면(위로 돌리면) 0이 되고, 값이 0인 다이얼은 감소하면(아래로 돌리면) D-1이 된다.
일련의 작업들은 다음의 조건을 만족한다:
- (i-1) 번째 작업에서 선택된 범위 [$l_{i-1}, r_{i-1}$]은 i번째 작업에서 선택된 [$l_i, r_i$]에 완전히 포함된다; 즉, $l_i \le l_{i-1} \le r_{i-1} \le r_i$이다. 초기 범위([$l_1, r_1$]) 는 마음대로 선택할 수 있다.
초기 조합이 [1, 1, 2, 2, 3, 3]인 자물쇠를 해제하기 위해 가능한 일련의 작업들의 가능한 예:
- 범위 [5, 6]을 위로 돌린다.
- 범위 [3, 6]을 위로 돌린다.
- 범위 [1, 6]을 위로 돌린다.
다음은 수행할 수 없는 작업이다:
- [6, 9] 다음 [1, 4] 회전, [6, 9]가 [1, 4]에 완전히 포함되지 않기 때문에($r_{i-1}=9$와 $r_i=4$에서 $r_{i-1} \le r_i$를 만족하지 않는다).
- [2, 7] 다음 [3, 6] 회전.
목표는 자물쇠의 모든 다이얼을 0으로 만들기 위해 필요한 가능한 작업들의 최소 횟수를 출력하는 것이다.
Input
입력의 첫째 줄에는 테스트 케이스의 개수, T가 주어진다. T개의 줄이 이어진다.
각 테스트 케이스는 2개의 줄을 가진다.
각 테스트 케이스의 첫째 줄은 각각 자물쇠의 다이얼 수와 다이얼의 크기를 나타내는 두 개의 정수 N, D를 포함한다.
각 테스트 케이스의 둘째 줄은 i번째 정수가 자물쇠의 초기 조합에서 i번째 다이얼을 의미하는 N개의 정수 $V_1, V_2, ..., V_N$이 주어진다.
Output
각 테스트 케이스에 대하여, x는 테스트 케이스의 번호(1부터 시작)이고 y는 자물쇠를 해제하기 위해 필요한 작업의 최소 횟수인 Case #x: y를 포함하는 하나의 줄을 출력하여라.
Limits
시간 제한: 30초.
메모리 제한: 1GB.
$1 \le T \le 100$.
$0 \le V_i \le D-1$, 모든 i에 대하여.
Test Set 1
$1 \le N \le 40$.
D = 2.
Test Set 2
$1 \le N \le 40$.
$2 \le D \le 10$.
Test Set 3
$1 \le N \le 400$.
$2 \le D \le 10^9$.
Sample
주의: 아래에 제출 시 실행되지 않는 추가 예제가 있다.
| Sample Input | Sample Output |
| 2 6 2 1 1 0 1 0 1 6 2 0 1 0 0 1 1 |
Case #1: 3 Case #2: 2 |
Sample Case #1에서, 자물쇠를 해제하기 위한 작업의 최소 횟수는 3이다. 다음 작업을 통해 해제할 수 있다:
- [4, 4]를 아래로 돌린다.
- [3, 5]를 아래로 돌린다.
- [1, 6]을 아래로 돌린다.
Sample Case #2에서, 자물쇠를 해제하기 위한 작업의 최소 횟수는 2이다. 다음 작업을 통해 해제할 수 있다:
- [3, 4]를 위로 돌린다.
- [2, 6]을 아래로 돌린다.
Additional Sample - Test Set 2
다음에 나오는 추가 예제는 Test Set 2의 제한에 알맞다. 제출 시 채점되지 않는다.
| Sample Input | Sample Output |
| 2 6 10 1 1 2 2 3 3 6 10 1 1 9 9 1 1 |
Case #1: 3 Case #2: 3 |
Sample Case #1에서, 자물쇠를 해제하기 위한 작업의 최소 횟수는 3이다. 다음 작업을 통해 해제할 수 있다:
- [5, 6]를 아래로 돌린다.
- [3, 6]를 아래로 돌린다.
- [1, 6]을 아래로 돌린다.
Sample Case #2에서, 자물쇠를 해제하기 위한 작업의 최소 횟수는 3이다. 다음 작업을 통해 해제할 수 있다:
- [3, 4]를 위로 돌린다.
- [3, 4]를 위로 돌린다.
- [1, 6]을 아래로 돌린다.
Tutorial
범위가 점점 커져야 하며, 범위 안에 있는 다이얼들이 같이 움직이기 때문에, 범위 안에 있는 숫자들을 전부 같게 만든 후, 범위를 확장시켜 나가야 된다는 것을 알 수 있다. 또한 테스트의 범위를 보면 $N \le 400, D \le 10^9$이므로 D로 푸는 것이 아닌 대략 $O(N^2)$ 정도로 풀어야겠다는 생각을 할 수 있다.
결론부터 말하면 DP로 해결할 수 있다. dp[l][r]을 "[l, r]을 하나의 숫자로 통일시키기 위한 최소 작업 횟수"라고 정의하자. 그러나 아직 부족하다. 하나의 숫자가 정해지지 않았기 때문이다. 그러나 범위를 확장시켜 나가는 것이기 때문에 $V_l$ 혹은 $V_r$로 통일시킬 것이라는 것을 알 수 있다. 즉, dp[l][r][x], 3차원으로 만들어 "x가 0이면 $V_l$로, x가 1이면 $V_r$로 만들기 위한 최소 작업 횟수"로 정의해주면 문제를 풀 수 있다.
같은 숫자가 연속해서 있는 경우, 범위를 한 번에 확장시킬 수도 있지만, 자물쇠를 돌리지 않은 채 범위를 한 칸씩 확장시켜 나간다고 생각해도 된다. 따라서 dp[l][r][x]를 구하기 위해선 dp[l+1][r][x]와 dp[l][r-1][x]만을 고려해도 된다. 여기서 조금 더 생각해보면 dp[l][r][0]을 구하기 위해선 dp[l+1][r][x]만을, dp[l][r][1]을 구하기 위해선 dp[l][r-1][x]만을 고려해도 된다는 것을 알 수 있다.
굳이 식으로 정리해보면 아래와 같다.
$
dp[l][r][0] = min(dp[l+1][r][0] + |V_l - V_{l+1}|, dp[l+1][r][1] + |V_l - V_r|)\\
dp[l][r][1] = min(dp[l][r-1][0] + |V_r - V_l|, dp[l][r-1][1] + |V_r - V_{r-1}|)\\
\\
|a - b| := 다이얼을 a에서 b로 만드는데 돌리는 최소 횟수
$
Solution
#include <bits/stdc++.h>
#define MAXN 410
using namespace std;
int d;
int v[MAXN];
long long dp[MAXN][MAXN][2];
bool chk[MAXN][MAXN];
void solve(int l, int r);
int diff(int x, int y);
int main()
{
int T, C, n, i, j, k;
cin >> T;
for(C=1; C<=T; C++){
cin >> n >> d;
for(i=0; i<n; i++){
cin >> v[i];
}
for(i=0; i<n; i++){
for(j=0; j<n; j++){
for(k=0; k<2; k++){
dp[i][j][k] = 0;
}
chk[i][j] = false;
}
}
solve(0, n-1);
long long _a, _b, ans;
_a = dp[0][n-1][0] + diff(v[0], 0);
_b = dp[0][n-1][1] + diff(v[n-1], 0);
ans = min(_a, _b);
cout << "Case #" << C << ": ";
cout << ans << '\n';
}
return 0;
}
void solve(int l, int r)
{
if(chk[l][r]) return;
if(l == r){
chk[l][r] = true;
return;
}
solve(l+1, r);
solve(l, r-1);
long long _a, _b;
// dp[l][r][0]
_a = dp[l+1][r][0] + diff(v[l], v[l+1]);
_b = dp[l+1][r][1] + diff(v[l], v[r]);
dp[l][r][0] = min(_a, _b);
// dp[l][r][1]
_a = dp[l][r-1][0] + diff(v[r], v[l]);
_b = dp[l][r-1][1] + diff(v[r], v[r-1]);
dp[l][r][1] = min(_a, _b);
chk[l][r] = true;
}
int diff(int x, int y)
{
return min((x-y+d)%d, (y-x+d)%d);
}
Hamiltonian Tour (15pts, 27pts)
Problem
Hamiltonian Tour (15pts, 27pts)
Kick Start - Google’s Coding Competitions
Hone your coding skills with algorithmic puzzles meant for students and those new to coding competitions. Participate in one round or join them all.
codingcompetitions.withgoogle.com
해밀턴은 토론토 옆에 있는 캐나다 도시이며, 도보 여행을 하기 좋은 곳이다.
이 문제에서, 해밀턴은 2R개의 행과 2C개의 열로 이루어진 격자로 표현된다. 격자의 각 셀은 비어있거나(*로 표현) 건물이 있다(#으로 표현). $1 \le i \le 2R, 1 \le j \le 2C$인 i행 j열에 있는 셀은 $A_{i,j}$로 표현된다. 건물이 있는 셀로 들어가는 것은 불가능하며, 현재 셀에서 변을 공유하는 인접한 셀로만 움직일 수 있다. 격자는 셀들이 $2 \times 2$ 블록으로 균등하게 나뉘며, 이 블록에 있는 4개의 셀은 모두 비어있거나 모두 건물을 가진다. $1 \le i \le R, 1 \le j \le C$에서 $A_{2i-1,2j-1}, A_{2i-1,2j}, A_{2i,2j-1}, A_{2i,2j}$ 셀은 $B_{i,j}$로 표현할 수 있다.
그레이스는 해밀턴 여행객이며 해밀턴에 있는 모든 빈 셀들을 방문하고 싶어 한다. 그레이스는 현재 $A_{1,1}$ 셀에 있다. 같은 셀을 두 번 방문하는 것은 그녀에게 지루한 일이다. 그러므로, 그레이스는 비어 있는 셀들을 정확히 한번 방문하고 마지막에는 $A_{1,1}$으로 오기를 원한다. 그레이스를 도와 그레이스나 모든 빈 셀을 한 번씩 방문하고 다시 $A_{1, 1}$으로 돌아오도록 하는 (각각 북, 동 , 남, 서를 나타내는 이동 방향 {N, E, S, W}를 포함하는)문자열을 제공해줄 수 있나요?
Input
입력의 첫째 줄에는 테스트 케이스의 수, T가 주어진다. T개의 테스트 케이스가 이어진다.
각 테스트 케이스의 첫째 줄에는 2개의 정수 R과 C가 주어진다.
각 테스트 케이스의 다은 R개의 줄에는 각각 C개의 문자가 주어진다.
i번째 줄의 j번째 문자는 블록 $B_{i,j}$를 나타내며, 이는 다음 네개의 셀을 의미한다: $A_{2i-1,2j-1}, A_{2i-1,2j}, A_{2i,2j-1}, A_{2i,2j}$.
만약 $B_{i,j} = \#$이면, $B_{i,j}$에 속한 네 개의 셀에는 건물이 세워진 것이다. 반대로 만약 $B_{i,j} = *$이면, $B_{i,j}$에 속한 네개의 셀은 비어 있다.
Output
각 테스트 케이스에 대하여, x는 테스트 케이스의 번호(1부터 시작)이고 y는 다음과 같은 문제의 답인 Case #x: y를 포함하는 하나의 줄을 출력하여라.
만약 문제의 해법이 없다면, y는 IMPOSSIBLE이 된다. 그렇지 않으면 Y는 가능한 움직임(각각 북, 동, 남, 서를 의미하는)을 뜻하는 {N, E, S, W} 문자로 이루어진 문자열이 된다. $A_{1,1}$에서 시작하며, 위에서 말한 대로 표현되어야 한다.
마지막 이동 후 $A_{1,1}$에 있어야 함에 유의하라; 이 움직임은 같은 셀을 두 번 방문한 것에 카운트되지 않는다.
만약 여러 해법이 있다면, 아무거나 출력하여라.
Limits
시간 제한: 25초.
메모리 제한: 1GB.
$1 \le T \le 100$.
$1 \le R \le 200$.
$1 \le C \le 200$.
격자의 모든 문자는 {#,*} 중 하나이다.
각 테스트 케이스의 입력 격자의 첫 번째 줄의 첫번째 문자는 * 문자이다, 즉 $B_{1,1}=*$이다.
Test Set 1
행과 열의 번호가 2로 나누어 떨어지면 그 블록은 건물을 가진다. (if and only if)
즉, $B_{i,j} = \# \Leftrightarrow ((i \bmod 2 = 0) and (j \bmod 2 = 0))$.
Test Set 2
추가적인 조건이 없다.
Sample
Note: 아래에 제출 시 실행되지 않는 추가 예제가 있다.
| Sample Input | Sample Output |
| 3 1 1 * 2 2 ** *# 3 4 **** *#*# **** |
Case #1: SENW Case #2: SSSENNEENWWW Case #3: ESSSSEEENNNWWNEEEEESWWSSSEESWWWWWWWNNNNN |
Additional Sample - Test Set 2
다음의 추가 예제는 Test Set 2의 제한에 알맞다. 반면에 코드 제출 시 실행되지는 않는다.
| Sample Input | Sample Output |
| 3 3 1 * * # 1 3 *#* 3 4 **#* **#* **** |
Case #1: SSSENNNW Case #2: IMPOSSIBLE Case #3: ESSSSENNNNESSSSEEENNNNESSSSSWWWWWWWNNNNN |
Tutorial
이 문제는 나에게 생각보다 쉬웠다. 미로에서 오른손 법칙(혹은 우수법)이라고 들어 봤는가? 미로를 탈출하기 위해 오른손을 벽에 짚고 벽을 따라가면 미로를 탈출할 수 있다는 법칙이다. 고등학교 탐구 논문 주제로 그래프를 다루며 이를 알게 되었고, 이번 문제를 푸는데 핵심이 된 법칙이다. 사실 오른손 법칙이 항상 미로를 탈출하는 방법도 아니고, 이 문제는 모든 곳을 가보는 게 목적이기 때문에 맞지 않을 수도 있다. 그래서 나는 한 번 지나간 곳은 벽으로 만들어버리는 트릭을 사용하여 이를 해결하였다.
대회 당시에는 논리 반 감 반으로 풀이를 떠올리고 풀었지만, 풀이엔 그렇게 적을 수 없으니 한번 이렇게 생각해보자. 우선 분명 출제자는 각 셀에 대한 정보를 주지 않고 셀 4개를 묶어 한 블록으로 준 이유가 있을 것이다. 나는 이를 "우측통행을 하기 위해서"라고 생각해보았다. 오른손 법칙은 갈림길에서 오른쪽을 우선으로 탐색한다 그리고 오른쪽 길이 막혔다면 그곳으로 다시 나온다. 만약 블록이 아니라 셀이었다면 같은 곳을 두번 가는게 되겠지만 길에 중앙선을 긋는다면 오른손을 벽에 짚었기 때문에 우측 통행을 하게 되었을 것이다. 즉, 셀을 4개씩 묶으면 우리는 우측 통행으로 셀을 중복해서 가지 않을 수 있게 되는 것이다.
우리는 우측 통행을 이용해 셀을 중복하지 않고 돌아다니는 것에 성공하였다. 좀 애매하다 가지 않은 곳이 있을 수도 있고, 빙빙 돌 수도 있지 않을까? 이것이 오른손 법칙의 약점이다. 그러나 앞서 말한 대로 이미 간 곳은 벽이라고 가정하면 이 문제도 해결이 된다.
생각보다 간단하지 않은가? 구현도 생각보다 간단하다. 일단 딱 봐도 dfs로 풀면 될 것 같다. 우리는 dfs에서 인자로 블록을 위치 x, y와 진행 방향 z까지 넘겨줌으로써 문제를 쉽게 해결할 수 있다. 방향 오른쪽을 기준으로 반시계 방향으로 돌면서 벽이 있는지 없는지를 검사하고, 없다면 해당 방향의 블록으로 이동해준다. 그리고 잘 생각해보면 우회전하냐, 직진하냐, 좌회전하냐, 후진하냐에 따라 꽤나 쉽게 문자열을 생성할 수 있다는 사실을 알 수 있을 것이다.
+ 풀이에서는 오른손 법칙이라 설명해 계속 오른손, 우측통행이라고 하였지만, 사실 나는 왼손을 기준으로 코드를 작성하였다. (큰 차이는 없다)
Solution
#include <bits/stdc++.h>
#define MAXR 210
#define MAXC 210
using namespace std;
int r, c;
bool b[MAXR][MAXC];
vector<char> ans;
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
char dir[4]={'N', 'E', 'S', 'W'};
void dfs(int x, int y, int z);
void move(int d1, int d2);
int main()
{
int T, C, i, j;
string str;
bool flag;
cin >> T;
for(C=1; C<=T; C++){
cin >> r >> c;
for(i=1; i<=r; i++){
cin >> str;
for(j=1; j<=c; j++){
if(str[j-1] == '*') b[i][j] = false;
else b[i][j] = true;
}
}
for(i=1; i<=r; i++) b[i][0] = b[i][c+1] = true;
for(j=1; j<=c; j++) b[0][j] = b[r+1][j] = true;
ans.clear();
dfs(1, 1, 1);
cout << "Case #" << C << ": ";
flag = true;
for(i=1; i<=r; i++){
for(j=1; j<=c; j++){
flag &= b[i][j];
}
}
if(flag){
for(i=0; i<ans.size()-1; i++) cout << dir[ans[i]];
cout << 'N';
cout << '\n';
}
else cout << "IMPOSSIBLE\n";
}
return 0;
}
void dfs(int x, int y, int z)
{
int d, last_d=z;
b[x][y] = true;
for(int k=0; k<4; k++){
d = (z+k-1+4)%4;
if(b[x+dx[d]][y+dy[d]]) continue;
move(last_d, d);
dfs(x+dx[d], y+dy[d], d);
last_d = (d+2)%4;
}
move(last_d, (z+2)%4);
}
void move(int d1, int d2)
{
// turn left
if((d1-1+4)%4 == d2){
ans.push_back(d2);
}
// go straight
if(d1 == d2){
ans.push_back(d1);
ans.push_back(d1);
}
// turn right
if((d1+1)%4 == d2){
ans.push_back(d1);
ans.push_back(d2);
ans.push_back(d2);
}
// go back
if((d1+2)%4 == d2){
ans.push_back(d1);
ans.push_back((d1+1)%4);
ans.push_back((d1+2)%4);
ans.push_back((d1+2)%4);
}
}
마치며...
오전 8시에 시작하는 대회였는데 늦잠을 자버리는 바람에 조금 늦게 시작했다. 시작부터 슬펐지만 큰 기대를 가지지 않은 대회였기에 편한 마음으로 문제를 풀기 시작하였다. 다행히도 문제가 생각보다 쉬웠고, 3번에서 멈칫하였지만 빠르게 dp를 생각해내서 1시간 만에 1, 2, 3번을 풀 수 있었다. 3번까지 풀고 4번의 정답자 수를 보자 너무 적어 Test Set 1번을 먼저 해결하고 남은 시간 Test Set 2를 풀어야겠다는 생각을 하였다. 그러나 풀이는 빠르게 생각해 냈지만 Test Set 1, 2를 따로 짜서 통과할 자신이 없었다. 그래서 우선 시간도 많이 남았으니 Test Set 2 풀이를 생각해보고 안되면 Test Set 1 코딩을 시작하기로 마음먹었다. 그러나 앞서 언급했듯이 고등학교 탐구 논문 시간에 조사했던 미로의 오른손 법칙 덕분에 풀이를 빠르게 생각해낼 수 있었으며, 막상 코딩을 해보니 코드도 간단하여 1시간 만에 4번까지 풀어내며 대회를 마무리하였다. 내가 과거 조사했던 것들이 문제 풀이에 큰 도움이 되었다는 사실에 짜릿했다.