[BOJ] 1987 : 알파벳
풀이
DFS
너무너무 쉬운문제지만 처음에 BFS로 접근해서 틀렸다.
말이 최대한 몇칸가는지 알아내는 문제였고,
‘최대한 찾는것은’ BFS로 하면 잘못 찾는다.
항상 그렇다고 볼수있을지는 모르겠지만,
‘최소’를 탐색하는것은 BFS
‘최대’를 탐색하는것은 DFS
으로 보통 풀리는것 같다.
코드
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
#include <cmath>
using namespace std;
const int dx[] = { 0,1,0,-1 };
const int dy[] = { 1,0,-1,0 };
char arr[20][20] = { 0 };
int r, c;
int alpha[150] = { 0 };
int ans = 1;
void dfs(int x,int y,int cnt) {
if (cnt > ans)
ans = cnt;
for (int dir = 0; dir < 4; dir++) {
int nx = x + dx[dir];
int ny = y + dy[dir];
if (nx >= 0 && nx < r&&ny >= 0 && ny < c&&alpha[arr[nx][ny]] == 0) {
alpha[arr[nx][ny]] = 1;
dfs(nx, ny, cnt + 1);
alpha[arr[nx][ny]] = 0;
}
}
}
int main() {
cin >> r >> c;
char tmp;
scanf("%c", &tmp);
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
scanf("%1c", &arr[i][j]);
}
scanf("%c", &tmp);
}
alpha[arr[0][0]] = 1;
dfs(0, 0, 1);
cout << ans;
return 0;
}
Written on March 31, 2019