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

문제 링크

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

 

오늘의 생각 : 시간 초과가 날때, 백트래킹 기준이 안보이면 방식을 바꿔보자.

---

◆문제 해결 및 설명◆

문제 해설 : 알파벳이 써있는 맵위 (0,0) 위치에서 출발하여 상하좌우로 움직일때, 새로 이동한 칸은 지금까지 지나온 모든 칸에 적혀있는 알파벳과 달라야 할때 최장거리를 구하여라

 

처음에는 맵을 나타내는 이차원 배열 map의 크기와 같게 visited 배열을 선언하고 못 가는 곳을 1로 설정해 dfs로 구현하였으나, 시간 초과로 인하여 visited를 일차원 배열로 설정 하였다.

Timeout

 

◆코드 전문◆

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int R, C, answer = 0;
vector<vector<char>> map;
vector<bool> visitied(200);
int dyx[] = {1, -1, 0, 0};

void dfs(int depth, int row, int col);

int main()
{
    cin >> R >> C;
    map = vector<vector<char>>(R, vector<char>(C));

    for (int i = 0; i < R; i++)
    {
        for (int j = 0; j < C; j++)
        {
            cin >> map[i][j];
        }
        cin.get();
    }

    dfs(1, 0, 0);
    cout << answer;
}

void dfs(int depth, int row, int col)
{
    if (visitied[map[row][col]])
    {
        return;
    }

    visitied[map[row][col]] = 1;
    for (int i = 0; i < 4; i++)
    {
        int ny = row + dyx[i];
        int nx = col + dyx[3 - i];
        if (ny >= 0 && ny < R && nx >= 0 && nx < C)
        {
            dfs(depth + 1, ny, nx);
        }
    }
    answer = max(answer, depth);
    visitied[map[row][col]] = 0;
    return;
}