[백준] 1987 알파벳 DFS

문제 :

www.acmicpc.net/problem/1987

1987번: 알파벳

분석 :

위 문제는 전형적인 DFS 문제이다. 

처음에는 오른쪽과 아래쪽으로 나아가는 것만 고려했고 수행한 알파벳은 set 함수에 저장해 놓아야지 생각하여 접근했었다. 하지만 안좋은 알고리즘이었다 하하

 

만약 진행 중 동일한 알파벳을 만난다면 진행한 것을 진행하지 않은 것처럼 하여 다른 방향으로 탐색하는 것이 포인트였다. 재귀함수 사용하는게 추상적이라 잘 이해가지 않아 다른 문제들도 많이 풀어봐야겠다. DFS, BFS는 모두 재귀로밖에 풀 수 없는건지도 궁금해졌다. 더 공부해봐야지 

 

++ 21.04.21 복습

문제에 명시된 "새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다." 이 구문을 통해 아 visit 를 설정해 같은 곳 방문하면 안되는 군! 하고 파악 할 수 있다.

 

c++ 코드 :

//
//  1987_DFS.cpp
//  SOMA👩🏻‍💻
//
//  Created by JoSoJeong on 2021/02/04.
//

#include <stdio.h>
#include <iostream>
#include <math.h>
using namespace std;

bool visit[26];
char arr[20][20];
int C, R;

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

int answer;

void DFS(int x, int y, int cnt){
    answer = max(answer, cnt);
    for(int i =0; i < 4; i++){
        int nx = x + dx[i];
        int ny = y + dy[i];
        if(nx >= 0 && ny >= 0 && nx < R && ny < C){
            if(visit[arr[nx][ny] - 'A'] == false){
                visit[arr[nx][ny] - 'A'] = true;
                DFS(nx, ny, cnt + 1); // 방문했으므로 cnt + 1
                visit[arr[nx][ny] - 'A'] = false; //재귀적으로 다 돌고 왔을 때 다시 시작 노드의 인접 노드 방문 위해서
            }
        }
    }
}

int main(){
    
    cin >> R >> C;
    for(int i = 0; i < R; i++){
        for(int j = 0; j < C; j++){
            cin >> arr[i][j];
        }
    }
    
    visit[arr[0][0] - 'A'] = true;
    DFS(0,0,1);
    cout << answer << endl;
    return 0;
}

    
//    char horse = arr[0][0];
//    char next;
//    set<char> nt;
//    nt.insert(horse);
//    int i = 0;
//    int j =0;
//    int count = 1;
//    while(i < C && j < R){
//        next = arr[i][++j];
//        //cout << "next0 " << next <<endl;
//
//        if(horse == next){
//            if(*nt.find(next)){
//                break;
//            }
//            next = arr[++i][--j];
//            //cout << "next1 " << next <<endl;
//            if(horse == next){
//                //cout << "next2 " << next <<endl;
//                break;
//            }else{
//                if(*nt.find(next)){
//                    break;
//                }
//            }
//            nt.insert(next);
//
//        }else{
//            if(*nt.find(next)){
//                break;
//            }
//        }
//        count++;
//        horse = next;
//    }
//    cout<< count << endl;