[ 실패 코드 ]
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int ans;
char board[5][5];
bool isused[5][5];
int dx[4] = {0,1,0,-1};
int dy[4] = {1,0,-1,0};
void func(int y, int x ,int depth, int Scnt){
if(depth == 7){
if(Scnt >= 4) ans++;
}else{
for(int dir=0;dir<4;dir++)
{
int ny = y + dy[dir];
int nx = x + dx[dir];
if(ny <0 or nx <0 or nx>= 5 or ny >= 5) continue;
if(isused[ny][nx]) continue;
isused[ny][nx] = true;
if(board[ny][nx] == 'S') func(ny, nx, depth+1, Scnt+1);
else func(ny, nx, depth+1, Scnt);
isused[ny][nx] = false;
}
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
for(int i=0;i<5;i++)
for(int j=0;j<5;j++)
cin >> board[i][j];
for(int i=0;i<5;i++)
for(int j=0;j<5;j++)
{
isused[i][j] = true;
if(board[i][j] == 'S') func(i, j, 1, 1);
else func(i, j, 1, 0);
isused[i][j] = false;
}
cout << ans;
return 0;
}
- 분석 이유
: 백트래킹이 내가 생각한 경우의수를 만족시키지 않아서 분석할 가치가 있다고 생각
- 로직
1) 모든 점
들에 대해 4방향
으로 백트래킹
실시
2) depth == 7
이고 'S'가 4개 이상
이면 ans++
- 실패 이유
1) 해당 코드는 하나의 막대처럼 검사해서, 중간에 뻗어나가는 경우는 검사하지 못한다
2) 시작은 다르지만, 같은 경우의수가 생김
: 모든 점에 대해 검사하는 해당 코드에서 시작은 다르지만 결과적으로 같은 경우가 되는 중복이 발생
--> 중복검사 하면 된다.(하지만 어차피 1번때문에 아예 걸러도 정답처리가 안됐었다)
[ 정답 코드 ]
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
char board[5][5];
int ch[25], ans;
vector<pair<int,int>> tmp(7);
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
bool check(){
bool b[5][5];
bool vis[5][5];
queue<pair<int,int>> q;
for(int i=0;i<5;i++)
{
fill(b[i], b[i]+5, false);
fill(vis[i], vis[i]+5, false);
}
for(int i=0;i<tmp.size();i++)
{
auto cur = tmp[i];
b[cur.first][cur.second] = true;
}
q.push({tmp[0].first, tmp[0].second});
vis[tmp[0].first][tmp[0].second] = true;
int cnt=1;
int scnt=0;
if(board[tmp[0].first][tmp[0].second] == 'S') scnt++;
while(!q.empty())
{
auto cur = q.front(); q.pop();
for(int dir=0;dir<4;dir++)
{
int ny = cur.first + dy[dir];
int nx = cur.second + dx[dir];
if(ny<0 or nx<0 or ny>=5 or nx>=5) continue;
if(vis[ny][nx] or !b[ny][nx]) continue;
q.push({ny, nx});
vis[ny][nx] = true;
cnt++;
if(board[ny][nx] == 'S') scnt++;
}
}
if(cnt == 7 and scnt >= 4) return true;
else return false;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
for(int i=0;i<5;i++)
for(int j=0;j<5;j++)
cin >> board[i][j];
fill(ch, ch+25, 1);
for(int i=0;i<7;i++) ch[i] = 0;
do{
int tc=0;
for(int i=0;i<25;i++)
if(!ch[i])
tmp[tc++] = {i/5, i%5};
if(check()) ans++;
}while(next_permutation(ch, ch+25));
cout << ans;
return 0;
}
- 로직
1) 25개중 7개를 고르는 조합을 구한다 (next_permutation
)
2) 7개의 점을 좌표화 해서 각 점들이 이어져있으며, 'S'
가 4개 이상있는지 검사한다
3) 1~2를 반복해서 ans++
- 후기
BFS로 검사하고 이런게 상당히 귀찮을것같았는데 막상 오래 안걸리고,
그냥 확실한 풀이가 떠오르면 바로 구현에 들어가는 것이 좋을것 같다 (시간초과는 고려해야함)