[백트래킹][dfs] 1987 알파벳 c++ 구현

목차

문제

 

코드 구현 시 주의점

처음에 거리를 인수로 전달하지 않고 전역변수로 해서 틀렸다.

그렇게 하면 백트래킹을 했을 때 호출 시점의 값으로 돌아가지 않기때문이다.

아래는 잘못된 방식이다.

int dx[4] = { 0, 0, 1, -1 };
int dy[4] = { 1, -1, 0, 0 };
int R, C;
char board[22][22] = { 0 };
int visit[22][22] = { 0 };
int maxd = 1;
int d =0;
map<char, int> m;


void dfs(int x, int y){
    d++;
    visit[y][x] = d;
    m[board[y][x]] = 1;

    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (nx < 0 || nx >= C || ny < 0 || ny >= R)
            continue;
        if (visit[ny][nx] == 0 && !m[board[ny][nx]]) {
            dfs(nx, ny, d);
        }
    }
    maxd = max(d, maxd);
    //이렇게 해준다고 하더라도 다른 dfs의 재귀호출때문에 문제가 생길 수 있다
    d--;
    visit[y][x] = 0;
    m[board[y][x]] = 0;
}

 

 

올바른 코드 구현

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
using namespace std;

int dx[4] = { 0, 0, 1, -1 };
int dy[4] = { 1, -1, 0, 0 };
int R, C;
char board[22][22] = { 0 };
int visit[22][22] = { 0 };
int maxd = 1;  //처음은 무조건 방문하기 때문에 기본값은 1이다
map<char, int> m;

//d를 인수로 전달해주어서 백트래킹을 한다
void dfs(int x, int y, int d) {
    d++;
    visit[y][x] = d;
    m[board[y][x]] = 1;

    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (nx < 0 || nx >= C || ny < 0 || ny >= R)
            continue;
        if (visit[ny][nx] == 0 && !m[board[ny][nx]]) {
            dfs(nx, ny, d);
        }
    }
    maxd = max(d, maxd);
    visit[y][x] = 0;
    m[board[y][x]] = 0;
}

int main() {
    cin >> R >> C;
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            cin >> board[i][j];
        }
    }
    //재귀 호출을 통해 인수 전달해야함
    dfs(0, 0, 0);
    cout << maxd;

    return 0;
}

 

다른 방식으로 재귀한 코드 구현

재귀는 많이해봐야 아는 것 같다..

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
using namespace std;

int dx[4] = { 0, 0, 1, -1 };
int dy[4] = { 1, -1, 0, 0 };
int R, C;
char board[22][22] = { 0 };
int visit[22][22] = { 0 };
int maxd = 1;
map<char, int> m;

void dfs(int x, int y, int d) {
    maxd = max(d, maxd);
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (nx < 0 || nx >= C || ny < 0 || ny >= R)
            continue;
        if (visit[ny][nx] == 0 && !m[board[ny][nx]]) {
            visit[ny][nx] = 1;
            m[board[ny][nx]] = 1;
           
            dfs(nx, ny, d+1);
            visit[ny][nx] = 0;
            m[board[ny][nx]] = 0;
        }
    }
}

int main() {
    cin >> R >> C;
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            cin >> board[i][j];
        }
    }
    visit[0][0] = 1;
    m[board[0][0]] = 1;
    dfs(0, 0, 1);
    cout << maxd;

    return 0;
}

 

비트마스킹을 이용한 방법

#include <iostream>
#include <algorithm>
using namespace std;
int R, C, ret, ny, nx;
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 num, int cnt){
    ret = max(ret, cnt);
    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 = (1 << (int)(a[ny][nx] - 'A'));
        if((num & _next) == 0) go(ny, nx, num | _next, cnt + 1);
    }
    return;
}
int main(){
    cin >> R >> C;
    for(int i = 0; i < R; i++){
        for(int j = 0; j < C; j++){
            cin >> a[i][j];
        }
    }
    go(0, 0, 1 << (int)(a[0][0] - 'A'), 1);
    cout << ret << '\n';
    return 0;
}