알고리즘 종류
: 백트래킹
최근 풀이 : 241106
https://www.acmicpc.net/submit/1987/86119838
-
백트래킹으로 접근해야 겠다는 판단을 함.
-
기저 사례를 만들고, bfs 처럼 4방면을 재귀하면서 방문을 진행하도록 작성함.
-
첫번째 0,0은 무조건 기준으로 해서 진행하므로, cnt는 1로 넣어줌.
-
방문 처리는 기저사례 조건에 진입하지 못한 경우, 방문 처리를 했다.
0,0 은 반드시 true니까. 굳이 false 할 필요 없고, 다음 지역으로 가는 친구들은 백트래킹해서 돌아와야 하니까. go 호출 다음에야 false 처리하도록 만듦.
vector<vector<char>> v;
vector<bool> check;
vector<pair<int, int>> dir
= { {-1,0},{1,0},{0,-1},{0,1} }; // 상하좌우
int r, c;
int res = 0;
void go(int _y, int _x, int _cnt)
{
// 기저 사례
char word = v[_y][_x];
if (check[word - 'A'] == true)
{
if (res < _cnt)
res = _cnt;
return;
}
// 그와 동시에 방문 하지 않았따면 여기서 true
check[word - 'A'] = true;
// 상하좌우에 탐색을 진행한다.
// 그런데 이미 체크되어 있네?? 그럼 복귀하고
// 다른 방면으로의 탐색을 해야 한다.
for (int i = 0; i < 4; ++i)
{
int nextY = _y + dir[i].first;
int nextX = _x + dir[i].second;
// 범위 체크
// 내부의 값을 확인해서 check되어 있는지를 확인하자.
if (nextY < 0 || nextY >= r)
{
if (res < _cnt)
res = _cnt;
continue;
}
if (nextX < 0 || nextX >= c)
{
if (res < _cnt)
res = _cnt;
continue;
}
char word = v[nextY][nextX];
if (check[word - 'A'] == true)
{
if (res < _cnt)
res = _cnt;
continue;
}
// 여기다가 하면 안된다.
//check[word - 'A'] = true;
go(nextY, nextX, _cnt + 1);
// 어차피 맨위의 기저사례에서 뛰쳐 나오면 여기로 오니까.
// 여기서 false 처리함.
check[word - 'A'] = false;
}
}최근풀이 : 241025
-
아무래도 이 부분인 것 같고. 방문체크를 해서 string.find 하는 부분을 지우자. 왜냐하면 1 < r, c < 20 이어서 시간복잡도 40이다.
변경 : 241025
-> 완전 탐색이기 때문에 check 불변수로 on -> 재귀 -> off 방식으로 진행했다.
잘못된 부분
: c에서 오른쪽으로 간다고 하자 그러면 c->a->a 에서 복귀를 한다.
-
그거를 이미 복귀했으니까. false로 하게 되면,
c -> a 이고 여기서 아래 부분과 왼쪽을 확인하기만 하면된다. -
그런데 나는 또 다시 false 된상태니까 여기서 또 재귀를 돌리는 시퀀스를 작성했는데 잘못되었다...
: 생각 좀 하고 작성하자....
정답 코드
https://www.acmicpc.net/submit/1987/85641650
풀이전략 : 240123
: 상하좌우로 움직이면서 , 복귀 과정도 거치면서 최대값을 구하는 것이기 때문에
백트래킹을 해야 한다고 판단!
- C에서 오른쪽 A로 갔다가 오른쪽 진행하려고 하는데, 이미 A니까 복귀해야 함.
그리고 나서 D로 향함.
-> 이런식으로 진행 즉, 상화좌우 움직임, 그리고 복귀, 이어서 나머지 하좌우 움직임.
-
알파벳은 대문자만 사용한다고 해서 bool[26] 으로 진행함.
-
시작점이 좌측 상단인 0,0 은 시작할때부터 visited = true 처리해서 복귀 동작 못하게 설정함.
-
복귀 동작 처리하기 위해서 내가 이미 거쳐온 visited 를 다시 원복해야 함.
-> 그래야 다른 정점에서 진행할 때 방문 할 수 있기 때문임. -
goo 함수 진입할 때마다 최대값 갱신도 하자.
결과
: 얍!
재채점 되면서 틀린듯함.
풀이전략
: c -> a -> d -> c로 최대 3번 이동이 가능한데,
c -> a-> a: 에서 다시 복귀 후, 이런식으로 진행을 하면서 최대값을
구하는 문제임.
=> 백트래킹이다.
- dfs 함수 반환값을 어떻게 처리할지가 관건이었음.
: 잘 고민해보면 답이 나옴.
최근 코드
- 220906 화
- // 19:26 ~ 19:45
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;
// 1987 알파벳
// 19:26 ~ 19:45
bool check[27];
int r, c;
// 상하좌우
int dy[]{ -1,1,0,0 };
int dx[]{ 0,0,-1,1 };
int res = -1;
//최대 몇번 이동하는지를 카운티하자.
int dfs(vector<vector<char>>&word , int y, int x, int cnt)
{
// 종료 조건
int node = word[y][x] - 'A';
if (check[node] == true)
{
return cnt;
}
for (int i = 0; i < 4; ++i)
{
int nextY = y + dy[i];
int nextX = x + dx[i];
// 테두리 체크
if (nextY < 0 || nextY >= r
|| nextX < 0 || nextX >= c)
{
continue;
}
check[node] = true;
res = max(res, dfs(word, nextY, nextX, cnt + 1));
check[node] = false;
}
return cnt;
}
int main()
{
cin >> r >> c;
// 말이 최대한 몇칸을 지날수 있는지를 출력하라.
// 대문자만 입력됨.
vector<vector<char>>v(r, vector<char>(c));
for (int i = 0; i < r; ++i)
{
string ss;
cin >> ss;
for (int j = 0; j < c; ++j)
{
v[i][j] = ss[j];
}
}
// 시작은 무조건 0,0
dfs(v, 0, 0, 0);
cout << res << endl;
}문제가 된 점...
- 변수 idx를 n이라고 써서 문제가 됬음...
- 백트래킹을 하면서, 정점을 이동해야 하는데, 어떻게 해야 할지 혼란스러웠음.
최근 코드
#include <iostream>
using namespace std;
#include <vector>
#include <string>
#include <algorithm>
int n, m;
int res = 0;
int cnt = 0;
//상하좌우
int dx[]{ 0,0,-1,1 };
int dy[]{ -1,1,0,0 };
void backTracking(vector<vector<char>>&v , vector<bool>&check
,int y, int x)
{
// 1. 종료 조건 만들기
//for (int i = 0; i < n; ++i)
{
//for (int j = 0; j < m; ++j)
{
int idx = v[y][x] - 'A';
// 상태 on, off
// 움직일 수 있다는 것을 의미함.
if (check[idx] == false)
{
++cnt;
check[idx] = true;
// 인접한 부분으로 이동을 해야 함.
for (int i = 0; i < 4; ++i)
{
int ny = y + dy[i];
int nx = x + dx[i];
//조건 체크
if (ny < 0 || ny >= n ||
nx < 0 || nx >= m)
{
continue;
}
//cout << ny << " " << nx << endl;
//cout << cnt << endl;
backTracking(v, check, ny, nx);
}
--cnt;
check[idx] = false;
}
// 상태가 on을 발견한다면?
else
{
// 간 거리를 확인해야 함.
res = max(res, cnt);
return;
}
}
}
}
void dfs(vector<vector<char>>&v , int y , int x)
{
for (int i = 0; i < 4; ++i)
{
int ny = y + dy[i];
int nx = x + dx[i];
//조건 체크
if (ny < 0 || ny >= n ||
nx < 0 || nx >= m)
{
continue;
}
dfs(v, ny, nx);
}
}
int main()
{
cin >> n >> m;
vector<vector<char>>v(n, vector<char>(m));
// 대문자 알파벳이므로,
vector<bool>check(26);
for (int i = 0; i < n; ++i)
{
string s;
cin >> s;
for (int j = 0; j < m; ++j)
{
v[i][j] = s[j];
}
}
// 백트래킹으로 가야함.
backTracking(v, check, 0, 0);
//cout << "result : ";
cout << res << endl;
}
첫번째 코드
#include <iostream>
#include <vector>
using namespace std;
int arr[26]{ 0, };
int r, c;
// 상하좌우
int dx[]{0,0,-1,1};
int dy[]{1,-1,0,0};
int mmin = 0;
void dfs(vector<vector<char>>_v , int _y, int _x, int &cnt)
{
//r은 y값 , c는 x값
if (_y < 0 || _y >= r || _x < 0 || _x >= c)
{
if (mmin < cnt)
mmin = cnt;
return;
}
if (arr[_v[_y][_x] - 'A'] == 0)
{
++cnt;
++arr[_v[_y][_x] - 'A'];
}
// 두번 이상 지나려고 할 경우 반환.
else
{
if (mmin < cnt)
mmin = cnt;
//종료
return ;
}
// 하로
dfs(_v, _y + 1, _x, cnt);
// 상으로
dfs(_v, _y - 1, _x, cnt);
// 우로
dfs(_v, _y , _x + 1, cnt);
// 좌로
dfs(_v, _y , _x - 1, cnt);
}
int main()
{
cin >> r >> c;
vector<vector<char>>v(r, vector<char>(c));
for (int i = 0; i < r; ++i)
{
for (int j = 0; j < c; ++j)
{
cin >> v[i][j];
}
}
/*
for (int i = 0; i < r; ++i)
{
for (int j = 0; j < c; ++j)
{
cout << v[i][j];
}
cout << endl;
}
*/
for (int i = 0; i < r; ++i)
{
for (int j = 0; j < c; ++j)
{
memset(arr, sizeof(arr), 0);
int result = 0;
dfs(v, i, j, result);
//if (mmin < a)
// mmin = a;
}
}
cout << mmin;
}-> 결과
입력 1,2번은 맞았지만, 3번 틀림.
3번 답은 10인데, 나의 결과는 6이 나옴...
무엇이 잘못되었을까???
: 내가 푼 방식은 , 이전으로 복귀 했을때 초기화를 해야 하는데,
초기화를 하지 못하는 방식임.
-> 이전으로 복귀한 후 다시 상화좌우 진행했을 때 최대의 루트가
나올 수 있다라는 것을 생각할 수 있어야 함.
백트래킹
: dfs 앞 뒤에서 인자로 사용된 체크 값에 대해서 true와 false 를 설정해야 함.
백트래킹을 하는 알고리즘을 습득해야 함.
