#include <iostream> #include <vector> #include <string> using namespace std; int dx[] = { 0, 0, 1, -1 }; int dy[] = { 1, -1, 0, 0 }; int go(vector<string> &board, vector<bool> &check, int x, int y) { int ans = 0; for (int k = 0; k<4; k++) { int nx = x + dx[k]; int ny = y + dy[k]; if (nx >= 0 && nx < board.size() && ny >= 0 && ny < board[0].size()) { if (check[board[nx][ny] - 'A'] == false) { check[board[nx][ny] - 'A'] = true; int next = go(board, check, nx, ny); if (ans < next) { ans = next; } check[board[nx][ny] - 'A'] = false; } } } return ans + 1; } int main() { int n, m; scanf("%d %d", &n, &m); vector<string> board(n); for (int i = 0; i<n; i++) { cin >> board[i]; } vector<bool> check(26); check[board[0][0] - 'A'] = true; printf("%d\n", go(board, check, 0, 0)); return 0; } |
필요한 것들 입력받고, 문자를 처리하는 방법에 대해서 알게됨.
그리고 기본적으로 dfs 의 틀이 있는 것 같다. 맵과, 체크를 넣고, x, y 위치 정보를 넣고, 이렇게 4개가 필요하다. 그리고 원하는 값에 대해서 ans 를 선언하고, return 값은 ans+1 로 dfs 를 한번 돌게 되면 +1 이 된다. 이 문제의 경우, 최대값을 찾느 문제이다. 4방향으로 돌리는 for문을 작성한다.
다음 칸이 맵안에 들어오면,
다음 칸이 간 적이 없으면,
갔다고 표시하고, 그 칸에 대해서 다시 dfs 를 돌린다. 그리고 리턴 다음에
기존의 ans 와 비교를 해서 어떤 값이 큰 값인지 찾아낸다.
갔던 칸에 대해서 다시 false 처리를 하므로써, 다른 dfs 에 방해가 되지 않도록 처리한다.
return 문의 위치, 원상 복귀를 필요로 하는 지정을 설정해주는 부분을 명확히 알게 된다.
오케이 이 문제에 대해서 명확히 알것.