[백준/C++] 알파벳_1987

📝 문제

https://www.acmicpc.net/problem/1987

💻 코드

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


using namespace std;

int r, c;
vector<vector<char>> arr(21, vector<char>(21));
vector<int> used; // 이미 지난 것
int ans = 0; // 지난 칸 수

void dfs(int row, int col, int cnt) {
    int dr[] = { 0, 0, 1, -1 };
    int dc[] = { 1, -1, 0, 0 };

    
    ans = max(cnt, ans);

    for (int i = 0; i < 4; i++) {
        int nextRow = row + dr[i];
        int nextCol = col + dc[i];
        if (nextRow < 0 || nextCol < 0 || nextRow >= r || nextCol >= c) continue;
        auto target = find(used.begin(), used.end(), int(arr[nextRow][nextCol]));
        if (target != used.end()) continue; // 이미 존재한다.
        used.push_back(arr[nextRow][nextCol]);
        dfs(nextRow, nextCol, cnt + 1);
        used.pop_back();
    }

    return;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> r >> c;
    
    for (int i = 0; i < r; i++) {
        string temp;
        cin >> temp;
        for (int j = 0; j < temp.size(); j++) {
            arr[i][j] = temp[j];
        }
    }

    used.push_back(arr[0][0]); // 시작한 거 추가
    dfs(0, 0, 1);

    cout << ans;

    
    return 0;
}

📌 해결방법

1. dfs로 이미 지나간 알파벳을 제외하면서 탐색

💡 배운 점

1. 문자의 2차열 배열을 vector로 입력받는 방법
   vector<vector> arr(21, vector(21));
   char arr[21][21]로 했으면 간단한 것을 vector로 하려다가 많이 헷갈림...
2. algorithm 헤더의 find와 find_if를 통해 배열, vector와 같은 일련의 데이터 구조에서 존재 유무를 판별할 수 있다.

✔ 느낀 점

오랜만에 문자 관련 퀴즈를 풀어서 어려웠다. 나의 하나 뿐인 이웃 new rice님의 풀이를 보고 in vector를 사용해서 넘을 수 없는 벽을 심어주고 싶었지만, 나도 실패했다 쩝,,,
그리고 풀면서 조심해야 할 점은 경로가 다양해야 하니깐 pop_back()을 꼭 해줘야한다!! 이것을 안해줘서 값이 이상하게 나왔다.