1987 : 알파벳 - DFS, BFS

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

1987번: 알파벳

 

문제요약

밟지 않은 새로운 알파벳 칸으로만 갈 수 있을 때, 이동할 수 있는 최대 칸

 

난이도

Gold 4

---

풀이 포인트

• DFS 활용
  • 이전 글자와 중복 체크

---

REVIEW

 

아직 문제가 주어졌을 때, bfs와 dfs중 무엇을 선택해야할지 모르겠다.

dfs는 감이 오는데 bfs의 경우 아직 낯설다..

 

이 문제의 경우 string에 지나온 값들을 누적해주고 그것을 초기화할 시점을 잘못 짚어

모든 순회의 결과를 한 string에 누적하다보니 계속해서 오답이었다.

 

모범답안에서 재귀를 돌리고, 다음 순회에 관해서는 초기화하고

날을 잡고 dfs, bfs 디버깅을 깊게 해서 흐름을 좀 이해할 필요가 있음

---

CODE

 

#include <bits/stdc++.h>
using namespace std;

int R, C, ret, ny, nx, visited[30];
char a[21][21];

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

void go(int y, int x, int cnt){
    ret = max(ret, cnt);
    cout << "현재 ret은 " << ret <<'\n';

    for(int i = 0; i < 4; i++){
        ny = y + dy[i], nx = x + dx[i];

        // 오버플로우 체크
        if(ny < 0 || ny >= R || nx < 0 || nx >= C) continue;
        
        int next = (int)(a[ny][nx] - 'A');
        
        if(visited[next] == 0){
            visited[next] = 1; 

            cout << next << "가 새로운 글자라 넣겠다.\n";
            go(ny, nx, cnt + 1);

            //다음 순회에 대해선 또 초기화
            visited[next] = 0;  
        } 
    }

    return;
}

int main(){

    cin >> R >> C;

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

    visited[(int)a[0][0] - 'A'] = 1;
    go(0, 0, 1);

    cout << ret << '\n';
    return 0;
}