글 읽기 - DFS, 백트레킹 사용.. 반례좀 부탁드립니다 ㅠ

rladudrb1200 5년 전 0

일단 알파벳을 입력받아서 map 변수에 하나씩 넣구요.

그 값을 가지고 check하면서 DFS돌리고, 나올땐 백트레킹으로 check해제하고 그때 값도 1감소시킵니다.

예제랑 질문검색해서 나온 반례들 돌렸을 때 답이 제대로 나옵니다..

그치만 제출하면 틀렸다고 나오네요..

도저히 봐도 틀린부분을 몰라서 질문드립니다..

고수님들 틀린 부분이나 반례좀 찾아주시면 감사드리겠습니다.

#include <stdio.h>
#include <iostream>
#include <math.h>
#include <algorithm>
using namespace std;
char map[21][21];
int dx[] = {-1,0,1,0};
int dy[] = {0,1,0,-1}; //위,오른쪽,아래,왼쪽
bool check[30]; //알파벳체크
int cnt = 1; //그순간마다 저장
int ans = 1; //최대값

void init(int r, int c){
    string str;
    
    for (int i=0; i<r; i++) {
        cin >> str;
        for (int j=0; j<c; j++) {
            map[i][j] = str[j];
        }
    }
}

void DFS(int r, int c, int x, int y){
    int idx = map[x][y];
    check[idx] = true;
    
    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) {
            int new_alpa = map[nx][ny];
            
            if (check[new_alpa] == false) { //방문하지x
                cnt++;
                ans = max(cnt, ans);
                DFS(r, c, nx, ny);
            }
        }
    }
    
    check[idx] = false; //백트레킹
    cnt--; //백트레킹
    
}

int main(){
    int r,c;
    cin >> r >> c;
    
    init(r,c);
    DFS(r,c,0,0);
    
    cout << ans << '\n';
    
    return 0;
}

djm03178 5년 전 1

대문자는 아스키 코드에서 65~90의 값을 가집니다. 그러니 check 배열도 최소 91 이상의 크기가 되어야 합니다.
첫 칸에서 꼼짝도 못 할 경우 0이 출력되지만, 1이 정답입니다. ans의 초기값을 1로 바꿔주면 됩니다.

rladudrb1200 5년 전 0

djm03178 님 감사합니다!!

가장 기본적인 배열 크기에서 바보같은 실수를 했네요... 덕분에 잘 돌아갑니다!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

DFS, 백트레킹 사용.. 반례좀 부탁드립니다 ㅠ

rladudrb1200 5년 전 0

djm03178 5년 전 1

rladudrb1200 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말