[백준/C++] 17070번 풀이
업데이트:
문제 정보
- 문제 출처: 백준 온라인 저지
- 문제 링크: 17070번 문제
- 문제풀이 코드 GitHub 링크
- 제출 언어: C++17
풀이
문제
유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 번호이고, 행과 열의 번호는 1부터 시작한다. 각각의 칸은 빈 칸이거나 벽이다.
오늘은 집 수리를 위해서 파이프 하나를 옮기려고 한다. 파이프는 아래와 같은 형태이고, 2개의 연속된 칸을 차지하는 크기이다.
파이프는 회전시킬 수 있으며, 아래와 같이 3가지 방향이 가능하다.
파이프는 매우 무겁기 때문에, 유현이는 파이프를 밀어서 이동시키려고 한다. 벽에는 새로운 벽지를 발랐기 때문에, 파이프가 벽을 긁으면 안 된다. 즉, 파이프는 항상 빈 칸만 차지해야 한다.
파이프를 밀 수 있는 방향은 총 3가지가 있으며, →, ↘, ↓ 방향이다. 파이프는 밀면서 회전시킬 수 있다. …
입력 요약
첫째 줄에 집의 크기 N(3 ≤ N ≤ 16)이 주어진다. 둘째 줄부터 N개의 줄에는 집의 상태가 주어진다. 빈 칸은 0, 벽은 1로 주어진다. (1, 1)과 (1, 2)는 항상 빈 칸이다.
출력 요약
첫째 줄에 파이프의 한쪽 끝을 (N, N)으로 이동시키는 방법의 수를 출력한다. 이동시킬 수 없는 경우에는 0을 출력한다. 방법의 수는 항상 1,000,000보다 작거나 같다.
코드
#include <stdio.h>
class PosData {
public:
int r, c, t, d;
PosData() {
r = c = t = d = 0;
}
PosData(int r, int c, int t, int d) {
this->r = r;
this->c = c;
this->t = t;
this->d = d;
}
PosData(PosData* posData) {
this->r = posData->r;
this->c = posData->c;
this->t = posData->t;
this->d = posData->d;
}
};
template <typename T>
class Stack {
public:
static const int SIZE = 16 * 16;
void push(T n) { arr[++top] = n; }
T pop() { return arr[top--]; }
bool isEmpty() { return top == -1; }
bool isFull() { return top == SIZE - 1; }
void init() { top = -1; }
void print() {
printf("\n");
for (int i = 0; i <= top; i++) {
printf("(%d, %d, %d, %d), ", arr[i].r, arr[i].c, arr[i].t, arr[i].d);
}
printf("\n");
}
private:
T arr[SIZE];
int top = -1;
};
int main() {
int n, cnt = 0;
scanf(" %d", &n);
int** a = new int*[n];
for (int i = 0; i < n; i++) a[i] = new int[n];
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
scanf(" %d", &a[i][j]);
Stack<PosData> stack = Stack<PosData>();
stack.push(PosData(0, 1, 0, 0));
PosData current, next;
while (!stack.isEmpty()) {
current = stack.pop();
while (current.d < 3) {
next = PosData(current);
if (next.d == 0 && next.t != 2 && next.c < n - 1 && a[next.r][next.c + 1] == 0) {
next.c++;
next.t = next.t == 2 ? 1 : 0;
next.d = 0;
if (next.r == n - 1 && next.c == n - 1) {
cnt++;
break;
}
current.d++;
stack.push(current);
current = PosData(next);
}
else if (next.d == 1 && next.c < n - 1 && next.r < n - 1 &&
a[next.r + 1][next.c + 1] == 0 && a[next.r + 1][next.c] == 0 && a[next.r][next.c + 1] == 0) {
next.r++;
next.c++;
next.t = 1;
next.d = 0;
if (next.r == n - 1 && next.c == n - 1) {
cnt++;
break;
}
current.d++;
stack.push(current);
current = PosData(next);
}
else if (next.d == 2 && next.t != 0 && next.r < n - 1 && a[next.r + 1][next.c] == 0) {
next.r++;
next.t = next.t == 0 ? 1 : 2;
next.d = 0;
if (next.r == n - 1 && next.c == n - 1) {
cnt++;
break;
}
current.d++;
stack.push(current);
current = PosData(next);
}
else {
current.d++;
}
}
}
printf("%d", cnt);
return 0;
}
설명
핵심은 구현 관점에서 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 번호이고, 행과 열의 번호는 1부터 시작한다. …를 만족하도록 로직을 구성하는 것입니다.
코드는 입력을 파싱한 뒤 조건 분기와 계산을 순서대로 수행하고, 문제에서 요구한 형식으로 결과를 출력합니다.
경계값과 예외 케이스도 함께 고려해 오답이 나기 쉬운 상황을 방지합니다.
댓글남기기