[백준][BOJ][C++][1987번] 알파벳

문제

세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다.

말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다.

좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 프로그램을 작성하시오. 말이 지나는 칸은 좌측 상단의 칸도 포함된다.

입력

첫째 줄에 R과 C가 빈칸을 사이에 두고 주어진다. (1 ≤ R,C ≤ 20) 둘째 줄부터 R개의 줄에 걸쳐서 보드에 적혀 있는 C개의 대문자 알파벳들이 빈칸 없이 주어진다.

 

코드

#include<iostream>
#include<algorithm>
using namespace std;
 
int R, C;
int ans;
bool visited[27];
char map[21][21];
int temp_map[21][21];
int p_x[4] = { 0,1,0,-1 };
int p_y[4] = { 1,0,-1,0 };
 
void printt(int cnt) {
    cout << cnt << "번째 " << endl;
    for (int y = 0; y < R; y++) {
        for (int x = 0; x < C; x++) {
            cout << temp_map[y][x] << " ";
        }
        cout << endl;
    }
    cout << endl;
}
 
void dfs(int x,int y, int cnt) {
    //printt(cnt);
    ans = max(ans, cnt);
    //cout << ans << endl;
    for (int i = 0; i < 4; i++) {
        int ny = y + p_y[i];
        int nx = x + p_x[i];
        if (ny < 0 || ny >= R || nx < 0 || nx >= C) continue;
        if (visited[map[ny][nx]-65]) continue;
        visited[map[ny][nx]-65] = true;
        //temp_map[ny][nx] = 1;
        dfs(nx, ny, cnt + 1);
        visited[map[ny][nx] - 65] = false;
        //temp_map[ny][nx] = 0;
    }
}
 
int main() {
    
    cin >> R >> C;
    for (int y = 0; y < R; y++) {
        std::string s;
        std::cin >> s;
        for (int x = 0; x < C; x++) {
            map[y][x]=s[x];
        }
    }
    
    /*for (int y = 0; y < R; y++) {
        for (int x = 0; x < C; x++) {
            cout << map[y][x]<<" ";
        }
        cout << endl;
    }*/
    ans = -1;
    visited[map[0][0] - 65]=true;
    //temp_map[0][0] = 1;
    dfs(0,0,1);
    cout << ans;
}
 
 

 

풀이

DFS를 사용해서 풀었습니다.

visited라는 배열을 알파벳 크기 보다 1크게 만들어 주었고 그것을 통해 이미 방문한 알파벳인지 파악하였습니다.

저장하는 방법은 A는 int로 65이기 때문에 배열에 저장할떄 65를 빼 주고 그 위치를 true로 넣어 방문한 알파벳을 표시하였습니다.