1987 알파벳 백트래킹 시도

작성한 질문수 19

0

기본적인 원복 패턴도 제대로 구현을 안 하고 질문을 했었네요... if(ret == 26)return; 딱 해당 코드만 추가했는데 바로 에러가 나와가지고 해당 코드에만 꽂혀서 기존 다른 코드에 문제가 있다는 생각을 못 했습니다.. 답변 감사합니다 !

0

안녕하세요 종현님 ㅎㅎ

백트래킹은 괜찮으나 코드 자체가 이상해서 UB가 뜨는 것 같습니다.

코드 자체가 좀 이상하면 분명 틀리지 않은 코드도 틀렸다고 뜨거든요.

고친 코드는 다음과 같은데요.

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

int n, m, visited[24][24], ret = -30, dy[4] = {-1, 0, 1, 0}, dx[4] = {0, 1, 0, -1};
char ar[24][24];
string s;

void dfs(int y, int x) {  
    if(ret == 26) return;
    for(int i=0; i<4; i++){
        int ny = dy[i] + y;
        int nx = dx[i] + x;
        if(ny < 0 || nx < 0 || ny >= n || nx >= m)continue;
        if(visited[ny][nx] || s.find(ar[ny][nx]) != string::npos)continue;
        
        visited[ny][nx] = 1;
        s += ar[ny][nx];
        dfs(ny,nx);
        visited[ny][nx] = 0;
        s.erase(s.size()-1, 1);
    }
    int size_ = s.size();
    if(ret < size_){
        ret = s.size();
    }
}
int main()
{
    cin >> n >> m;
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            cin >> ar[i][j];
        }
    }
    visited[0][0] = 1; 
    s += ar[0][0];
    dfs(0,0);
    cout << ret<< '\n';
    return 0;
}

백트래킹을 넣어도 맞습니다.

종현님의 코드를 보면.

void dfs(int y, int x) {
    if(ret == 26)return;
    visited[y][x] = 1;
    s += ar[y][x];
    // cout << s << '\n';
    for(int i=0; i<4; i++){
        int ny = dy[i] + y;
        int nx = dx[i] + x;
        if(ny < 0 || nx < 0 || ny >= n || nx >= m)continue;
        if(visited[ny][nx] || s.find(ar[ny][nx]) != string::npos)continue;
        dfs(ny,nx);
        visited[ny][nx] = 0;
        s.erase(s.size()-1, 1);

이렇게 되어있죠.

y, x를 칠하고.

그 다음 4방향, ny, nx를 방문미처리를 한다?

이상하지 않나요?

제가 알려드린 원복은

a를 칠하고

go()함수

a를 칠한 것을 없앤다.

이건데요. ㅎㅎ 약간 코드 자체가 이상한 로직을 가지니 UB가 되는 것 같습니다.

다만, 다른 부분은 괜찮게 짜셨습니다.

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제가 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.