Inflearn Community Q&A
asked
5-M 질문입니다.
Written on
·
302
0
선생님 안녕하세요.
http://boj.kr/9a2f81571b6d4daea656a37368a5ade2
rotate하는 방법을 생각하지 못해서 위, 아래, 왼쪽, 오른쪽 로직을 모두 작성해서 풀었습니다.
3
0 64 8
128 0 32
32 0 0위의 테스트케이스에서 문제를 발견했는데요. 위 -> 오 -> 아 -> 왼 -> 왼 순서로 진행하면 정답인 256이 나오게 됩니다.
up();
right();
down();
left();
left();
printA();이런 식으로 직접 순서를 따라갔을 때는 정상적으로 답이 나오는 걸 봐서 방향 로직이 문제는 아닌 것 같습니다.(좀 비효율적이지만 답은 나온다는 점에서요..)
따라서 제 백트래킹 함수가 모든 경우의 수를 다 탐색하지 않는다는 결론이 나오는데요... 왜 경우의 수를 모두 탐색하지 않는지를 모르겠습니다.
Answer 1
0
음 안녕하세요 yeon님ㅎㅎ
일단 백트레킹이란 워딩 자체가 모든 경우의 수를 탐색하지 않는다는 거니까.
질문을 바꿔서 얘기하자면
원래는 완탐으로 하려고 했는데 코드가 백트레킹이 되어버렸다. 이런게 아닐까요?
근데 코드의 어떤 부분이 백트래킹으로 구축했다고 말씀하시는건가요?
이문제는
최대 5번 이동해서 만들 수 있는 가장 큰 블록의 값을 구하는 프로그램을 작성하시오.
최대 5번 모두 움직여야 하는 완탐으로 풀어야 한다고 볼 수 있어요.
또한,
위의 테스트케이스에서 문제를 발견했는데요. 위 -> 오 -> 아 -> 왼 -> 왼 순서로 진행하면 정답인 256이 나오게 됩니다.
순서는 상관없습니다. 이 문제는. 모든 경우의 수를 탐색해야 하기 때문에 위위위위오 이런 경우의 수가 나와도 상관이 없어요.
음 그리고 코드를 보면... up() 함수에 대해 도와달라는 말씀이신가요?
감사합니다.
음.. 혹시 어떻게 디버깅을 하셨나요?
이 코드의 경우의 수는 5460 개 정도의 경우의 수가 나오는데요.(up, left .. 함수호출만 보면)
마지막 cnt_ret 참고해주세요.
혹시 디버깅 코드 올려주실 수 있으실까요?
#include <bits/stdc++.h>
using namespace std;
int n, a[21][21], b[21][21];
int ret = 0;
vector<int> press(vector<int> v) {
for (int i=1; i<v.size(); i++) {
if (v[i-1] == v[i]) {
v[i-1] += v[i];
v[i] = 0;
}
}
vector<int> tmp;
for (int i=0; i<v.size(); i++) {
if (v[i] != 0) tmp.push_back(v[i]);
}
return tmp;
}
void up() {
for (int j=0; j<n; j++) {
// 0보다 큰 원소만 배열에 넣는다.
vector<int> tmp;
for (int i=0; i<n; i++) {
if (a[i][j] > 0) tmp.push_back(a[i][j]);
}
// 같은 원소끼리 합친 뒤 0보다 큰 원소를 다시 모아서 리턴
vector<int> after = press(tmp);
// 0을 뒤에 추가해서 빈 공간을 채우기
/*
일단 임시로 n개 추가했습니다.
원래는 n - after.size()개를 추가해야 하는데 outbound 에러가 발생해서요..
*/
for (int i=0; i<n; i++) after.push_back(0);
// 결과값을 바탕으로 원본 배열 수정
int t = 0;
for (int i=0; i<n; i++) {
a[i][j] = after[t];
t++;
}
}
}
void down() {
for (int j=0; j<n; j++) {
vector<int> tmp;
for (int i=n-1; i>=0; i--) {
if (a[i][j] > 0) tmp.push_back(a[i][j]);
}
vector<int> after = press(tmp);
for (int i=0; i<n; i++) after.push_back(0);
int t=0;
for (int i=n-1; i>=0; i--) {
a[i][j] = after[t];
t++;
}
}
}
void right() {
for (int i=0; i<n; i++) {
vector<int> tmp;
for (int j=n-1; j>=0; j--) {
if (a[i][j] > 0) tmp.push_back(a[i][j]);
}
vector<int> after = press(tmp);
for (int i=0; i<n; i++) after.push_back(0);
int t=0;
for (int j=n-1; j>=0; j--) {
a[i][j] = after[t];
t++;
}
}
}
void left() {
for (int i=0; i<n; i++) {
vector<int> tmp;
for (int j=0; j<n; j++) {
if (a[i][j] > 0) tmp.push_back(a[i][j]);
}
vector<int> after = press(tmp);
for (int i=0; i<n; i++) after.push_back(0);
int t=0;
for (int j=0; j<n; j++) {
a[i][j] = after[t];
t++;
}
}
}
int cnt_ret = 0;
void bt(int cnt) {
if (cnt > 5) return;
int mb = a[0][0];
for (int i=0; i<n; i++) {
for (int j=0; j<n; j++) {
mb = max(mb, a[i][j]);
}
}
ret = max(ret, mb);
copy(&a[0][0], &a[0][0]+21*21, &b[0][0]);
for (int d=0; d<4; d++) {
cnt_ret++;
if (d == 0) up();
else if (d == 1) down();
else if (d == 2) left();
else if (d == 3) right();
bt(cnt+1);
copy(&b[0][0], &b[0][0]+21*21, &a[0][0]);
}
}
int main(){
cin >> n;
for (int i=0; i<n; i++) {
vector<int> tmp;
for (int j=0; j<n; j++) {
cin >> a[i][j];
}
}
bt(0);
cout << ret << "\n";
cout << cnt_ret << '\n'; // 5460
return 0;
}
#include <bits/stdc++.h>
using namespace std;
int n, a[21][21], b[21][21];
int ret = 0;
vector<pair<int, string>> records;
vector<int> press(vector<int> v) {
for (int i=1; i<v.size(); i++) {
if (v[i-1] == v[i]) {
v[i-1] += v[i];
v[i] = 0;
}
}
vector<int> tmp;
for (int i=0; i<v.size(); i++) {
if (v[i] != 0) tmp.push_back(v[i]);
}
return tmp;
}
void up() {
for (int j=0; j<n; j++) {
vector<int> tmp;
for (int i=0; i<n; i++) {
if (a[i][j] > 0) tmp.push_back(a[i][j]);
}
vector<int> after = press(tmp);
for (int i=0; i<n; i++) after.push_back(0);
int t = 0;
for (int i=0; i<n; i++) {
a[i][j] = after[t];
t++;
}
}
}
void down() {
for (int j=0; j<n; j++) {
vector<int> tmp;
for (int i=n-1; i>=0; i--) {
if (a[i][j] > 0) tmp.push_back(a[i][j]);
}
vector<int> after = press(tmp);
for (int i=0; i<n; i++) after.push_back(0);
int t=0;
for (int i=n-1; i>=0; i--) {
a[i][j] = after[t];
t++;
}
}
}
void right() {
for (int i=0; i<n; i++) {
vector<int> tmp;
for (int j=n-1; j>=0; j--) {
if (a[i][j] > 0) tmp.push_back(a[i][j]);
}
vector<int> after = press(tmp);
for (int i=0; i<n; i++) after.push_back(0);
int t=0;
for (int j=n-1; j>=0; j--) {
a[i][j] = after[t];
t++;
}
}
}
void left() {
for (int i=0; i<n; i++) {
vector<int> tmp;
for (int j=0; j<n; j++) {
if (a[i][j] > 0) tmp.push_back(a[i][j]);
}
vector<int> after = press(tmp);
for (int i=0; i<n; i++) after.push_back(0);
int t=0;
for (int j=0; j<n; j++) {
a[i][j] = after[t];
t++;
}
}
}
void bt(int cnt, string rec) {
if (cnt > 5) return;
cout << cnt << " " << rec << "\n";
int mb = a[0][0];
for (int i=0; i<n; i++) {
for (int j=0; j<n; j++) {
mb = max(mb, a[i][j]);
}
}
if (ret < mb) {
records.push_back({mb, rec});
}
ret = max(ret, mb);
copy(&a[0][0], &a[0][0]+21*21, &b[0][0]);
for (int d=0; d<4; d++) {
if (d == 0) {
up();
bt(cnt+1, rec+"위");
}
else if (d == 1) {
down();
bt(cnt+1, rec+"아");
}
else if (d == 2) {
left();
bt(cnt+1, rec+"좌");
}
else if (d == 3) {
right();
bt(cnt+1, rec+"우");
}
copy(&b[0][0], &b[0][0]+21*21, &a[0][0]);
}
}
int main(){
cin >> n;
for (int i=0; i<n; i++) {
vector<int> tmp;
for (int j=0; j<n; j++) {
cin >> a[i][j];
}
}
bt(0, "");
for (pair<int, string> it : records) {
cout << it.first << " " << it.second << "\n";
}
cout << ret << "\n";
return 0;
}디버깅 코드입니다!
bt함수에 rec이라는 파라미터를 추가해서 경로를 저장했고 매 턴마다 출력했습니다. (경로 조합이 정상적으로 나오는지 보기 위해서요)
if (ret < mb) {
records.push_back({mb, rec});
}
ret = max(ret, mb);이 부분은 최댓값을 갱신했을 때만 {현재 최댓값, 경로}를 저장하는 부분입니다. 테스트해 보니 함수를 처음 실행했을 때 딱 한 번 최댓값을 갱신한다는 사실을 알 수 있었습니다.
안녕하세요 yeon님 ㅎㅎ 디버깅 코드가 잘못된 거같아요. 일단 디버깅코드가 중간에 찍는 경우도 있긴 한데 지금 yeon님은 위우아좌좌가 나오는지. 를 확인하는 코드가 필요한거잖아요?
그러면 마지막 기저사례에 디버깅코드를 작성하는게 좋습니다.
아 참고로 pop_back() 3번한것은
pop_back() 한번 할 때마다 문자가 1바이트 단위로 빠지는데 한글이기 때문에 3바이트를 기준으로 한개 빼기 위해서 3번했어요.
코드는 다음과 같습니다.
#include <bits/stdc++.h>
using namespace std;
int n, a[21][21], b[21][21];
int ret = 0;
vector<pair<int, string>> records;
vector<int> press(vector<int> v) {
for (int i=1; i<v.size(); i++) {
if (v[i-1] == v[i]) {
v[i-1] += v[i];
v[i] = 0;
}
}
vector<int> tmp;
for (int i=0; i<v.size(); i++) {
if (v[i] != 0) tmp.push_back(v[i]);
}
return tmp;
}
void up() {
for (int j=0; j<n; j++) {
vector<int> tmp;
for (int i=0; i<n; i++) {
if (a[i][j] > 0) tmp.push_back(a[i][j]);
}
vector<int> after = press(tmp);
for (int i=0; i<n; i++) after.push_back(0);
int t = 0;
for (int i=0; i<n; i++) {
a[i][j] = after[t];
t++;
}
}
}
void down() {
for (int j=0; j<n; j++) {
vector<int> tmp;
for (int i=n-1; i>=0; i--) {
if (a[i][j] > 0) tmp.push_back(a[i][j]);
}
vector<int> after = press(tmp);
for (int i=0; i<n; i++) after.push_back(0);
int t=0;
for (int i=n-1; i>=0; i--) {
a[i][j] = after[t];
t++;
}
}
}
void right() {
for (int i=0; i<n; i++) {
vector<int> tmp;
for (int j=n-1; j>=0; j--) {
if (a[i][j] > 0) tmp.push_back(a[i][j]);
}
vector<int> after = press(tmp);
for (int i=0; i<n; i++) after.push_back(0);
int t=0;
for (int j=n-1; j>=0; j--) {
a[i][j] = after[t];
t++;
}
}
}
void left() {
for (int i=0; i<n; i++) {
vector<int> tmp;
for (int j=0; j<n; j++) {
if (a[i][j] > 0) tmp.push_back(a[i][j]);
}
vector<int> after = press(tmp);
for (int i=0; i<n; i++) after.push_back(0);
int t=0;
for (int j=0; j<n; j++) {
a[i][j] = after[t];
t++;
}
}
}
void bt(int cnt, string rec) {
if (cnt > 5){
rec.pop_back();
rec.pop_back();
rec.pop_back();
records.push_back({0, rec});
return;
}
int mb = a[0][0];
for (int i=0; i<n; i++) {
for (int j=0; j<n; j++) {
mb = max(mb, a[i][j]);
}
}
ret = max(ret, mb);
copy(&a[0][0], &a[0][0]+21*21, &b[0][0]);
for (int d=0; d<4; d++) {
if (d == 0) {
up();
bt(cnt+1, rec+"위");
}
else if (d == 1) {
down();
bt(cnt+1, rec+"아");
}
else if (d == 2) {
left();
bt(cnt+1, rec+"좌");
}
else if (d == 3) {
right();
bt(cnt+1, rec+"우");
}
copy(&b[0][0], &b[0][0]+21*21, &a[0][0]);
}
}
int main(){
cin >> n;
for (int i=0; i<n; i++) {
vector<int> tmp;
for (int j=0; j<n; j++) {
cin >> a[i][j];
}
}
bt(0, "");
for (pair<int, string> it : records) {
if(it.second == "위우아좌좌")cout << it.first << " " << it.second << "\n";
//cout << it.first << " " << it.second << "\n";
}
cout << ret << "\n";
return 0;
}
/*
3
2 2 2
4 4 4
8 8 8
0 위우아좌좌
0 위우아좌좌
0 위우아좌좌
0 위우아좌좌
16
*/
답변 감사합니다! 같은 방법으로 문제가 되었던 테스트케이스를 확인했는데 위우아좌좌 경로를 확인할 수 있었습니다. 그렇다면 최댓값을 구하는 로직이나 상태를 원복하는 로직에 문제가 있는지 확인해야겠네요.. 좀더 고민해보고 다시 질문드리겠습니다.
디버깅을 할 때 이 문제처럼 답이 이상하게 나오는 테스트케이스를 찾아냈고 정답이 나오는 경로도 알게 된 경우 마지막 기저사례에 디버깅 코드를 작성하면 유용할 것 같습니다. 그런데 이런 걸 찾지 못하고 뭔가 문제가 있는 건 알겠는데 어디가 문제인지 모를 경우에는 보통 디버깅을 어떻게 하나요? 전 지금까지 모든 디버깅을 중간에 찍어서 전부 확인해보는 식으로 했었습니다.
지금 이 문제 같은 경우 경우의 수가 5460개죠? (yeon님 기준) 그럴 경우에는 cnt가 5까지가 아니라 1정도부분까지 걸어서 잘되고 있나 확인을 합니다. 잘 돌아가고 있나 중간 중간 맵을 체크하구요. 모든 경우의 수는 절대 디버깅하지 못합니다.
cnt를 1로 걸든 2로 걸든 작은 경우의 수를 걸어서 확인해야 합니다.
다만, 제가 지금 끝에서 확인하는 (기저사례에서 확인한) 이유는 yeon님이 궁금해 하신 디버깅 자체가 "위우아좌좌"가 나오는지? 라는 질문이였기 때문에 해당 질문을 확인할 수 있는 효율적인 방법은 끝에서 확인하는 방법이였기 때문에 그리 한것이에요.
무조건 끝에서만 확인하지는 않으며 문제마다 다 다르고 저도 중간에 찍어보는 경우도 많아요. ㅎㅎ
감사합니다.
이 부분을 백트래킹 로직이라고 생각했는데 선생님 답변을 보고 생각해 보니 제 코드는 완전탐색이 맞는 것 같습니다. 말씀대로 모든 경우를 탐색하지 않는 것이 백트래킹인데 제 코드에는 가지치기하는 로직이 없으니까요. 앞으로는 용어를 명확하게 쓰도록 더 고민하고 질문하겠습니다!
탐색 순서는 상관 없다는 것은 알고 있습니다! 다만 제 코드가 완전탐색 코드라면 정답이 되는 조합(ex 위-오-아-왼-왼)이 한 번쯤은 나와야 할 것 같은데 그러질 않아서요. bt 함수가 왜 모든 경우를 탐색하지 않는지가 궁금합니다.
(+) up함수에 달아놓은 주석은 그냥 좀 편하게 보시라고 달아 놓은 것입니다. down, left, right는 up과 같은 구조로 이루어져 있어서 up에만 달았습니다!