728x90
https://www.acmicpc.net/problem/1987
처음에 BFS로 풀다가 답이 제대로 안 나와서 뭐지? 했는데 다시 문제를 읽어보니.. DFS로 풀었어야 했다!
근데 당연함. 한 루트로 쭉 가는 거니까... 멍청하게 시간만 버림.. BFS로ㅋ
내가 넘 좋아하는 BFS 날 배신하다니...
근데 DFS로 막연하게 풀면 안 풀린다. 왜냐면 알파벳 방문 체크를 이미 해줬기 때문에 한 루트만 가고 끝이 나기 때문..!!
여러 루트를 모두 둘러보고 가장 긴 루트를 골라야 하기 때문에 DFS 들어갔다가 나오면 알파벳 방문 체크를 풀어줘야 한다!
다른 문제를 풀어도 잊지 말고 꼭 기억하기!! (백트래킹)
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int r, c, ans;
char arr[21][21];
bool visit[21];
int dir[4][2] = {{1,0}, {0,1}, {-1,0}, {0,-1}};
void DFS(int x, int y, int cnt){
ans = max(ans, cnt);
for(int i=0; i<4; i++){
int dx = x + dir[i][0];
int dy = y + dir[i][1];
if(0<=dx&&dx<r&&0<=dy&&dy<c && !visit[arr[dx][dy] - 'A']){
visit[arr[dx][dy] - 'A'] = true;
DFS(dx, dy, cnt+1);
visit[arr[dx][dy] - 'A'] = false; //중요 부분!! (다른 방향으로도 이동해야 되기 때문에 꼭 해당 알파벳 방문 체크 해제 해야함
}
}
}
int main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> r >> c;
for(int i=0; i<r; i++) for(int j=0; j<c; j++) cin >> arr[i][j];
for(int i=0; i<r; i++) for(int j=0; j<c; j++) visit[arr[i][j]-'A'] = false;
visit[arr[0][0] - 'A'] = true;
DFS(0, 0, 1);
cout << ans << '\n';
return 0;
}
728x90
'알고리즘 > 백준' 카테고리의 다른 글
[백준/c++] 1285번: 동전 뒤집기 (0) | 2022.07.29 |
---|---|
[백준/c++] 13458번: 시험 감독 (0) | 2022.07.27 |
[백준/c++] 2661번: 좋은수열 (0) | 2022.07.26 |
[백준/c++] 3649번: 로봇 프로젝트 (0) | 2022.07.26 |
[백준/c++] 1747번: 소수&팰린드롬 (0) | 2022.07.25 |