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

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

DFS

알파벳으로 구성된 보드판에서 좌측상단부터 시작해서 중복되지 않은 칸을 지나면서 상하좌우로 이동할 수 있다.

이때 최대 몇칸까지 지날 수 있는지 구하는 문제

 

접근 방법

상하좌우 이동하는 경우들로 DFS로 풀었다.

 

오답노트

처음에 지나온 알파벳들을 기억하려고 벡터에 지나온 문자들을 담아두고 찾는 식으로 했다가 시간초과나서

알파벳 개수 (26)만큼 boolean 배열에 방문 여부 체크하면서 가는걸로 고쳤다.

 

아 그리고 visit 배열 처음에 0으로 초기화 안해줬더니 랜덤값 들어가던데 (아니 그냥 Int 배열은 다 0 들어가더만)

 

근데 왜 DFS함수 시작할 때 방문하는걸로 하면 왜 안될까유

그러면 visit배열을 다시 false로 바꿔주지 않아도 되는거 아닌가..암튼 

 

소스코드

#include <iostream>
using namespace std;

int dr[4] = {0, 1, 0, -1};
int dc[4] = {1, 0, -1, 0};
int result = 0;
char board[20][20];
int r, c;

void dfs(bool visit[], int cr, int cc, int num){
    result = result < num ? num : result;
    
    for(int i = 0 ; i < 4 ; i++){
        int nr = cr + dr[i];
        int nc = cc + dc[i];

        if(nr >= 0 && nr < r && nc >= 0 && nc < c && !visit[board[nr][nc]-'A']){
            visit[board[nr][nc]-'A'] = true;
            dfs(visit, nr, nc, num+1);
            visit[board[nr][nc]-'A'] = false;
        }
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin >> r >> c;
    for(int i = 0 ; i < r ; i++){
        for(int j = 0 ; j < c ; j++){
            cin >> board[i][j];
        }
    }
    
    bool visit[26] = {0,};
    visit[board[0][0]-'A'] = true;
    dfs(visit, 0, 0, 1);
    cout << result;
}