[C++] 백준 - 1987 : 알파벳

문제 링크

1987번: 알파벳

 

풀이 )

  여태까지 풀었던 dfs에서와 달리 방문한 칸을 저장하는 배열 대신, 사용한 알파벳을 저장하는 배열을 사용했다.

  처음 (0, 0)을 시작으로 방문한 칸의 알파벳의 사용 여부를 갱신하고, 4방향에 대해서 탐색한 최댓값+1(현재칸)을 반환한다.

  각 방향에 대해 영향을 주지 않기 위해 다음 방향을 가기 전에 다음 칸 알파벳의 사용 여부를 초기화해준다.

 

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};

int r, c;
vector<string> board;
bool used[26];

int dfs(int x, int y){
    int ret = 0;
    used[board[x][y]-'A'] = true;
    for(int dir = 0; dir < 4; ++dir){
        int xx = x+dx[dir];
        int yy = y+dy[dir];
        if(xx < 0 || xx >= r || yy < 0 || yy >= c)
            continue;
        if(used[board[xx][yy]-'A'])
            continue;
        ret = max(ret, dfs(xx, yy));
        used[board[xx][yy]-'A'] = false;
    }
    return ret+1;
}

int main(void){
    cin >> r >> c;
    for(int i = 0; i < r; ++i){
        string s;
        cin >> s;
        board.push_back(s);
    }

    int ans = dfs(0, 0);

    cout << ans;
}