글 읽기 - [C언어] 왜틀렸는지 모르겠습니다.. 게시판 반례 다 통과합니다

sc3289 2년 전 0

제가 놓치고 있는 부분이 뭔지 모르겠습니다....

게시판 반례도 다 확인했고 아무리 봐도 알고리즘적으로 문제가 뭔지 보이질 않습니다 ㅜㅜ

#include <stdio.h>

char board[21][21];
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
int visit[21][21]; // 경로 확인
int alpha[26]; // 알파벳 중복 체크
int max_y;
int max_x;
int max = 0;
void dfs(int,int,int);

int main()
{
    scanf("%d %d",&max_y,&max_x);
    getchar();
    for(int i=0;i<max_y;i++)
    {
        for(int j=0;j<max_x;j++)
            scanf("%c",&board[i][j]);
        getchar();
    }
    visit[0][0] = 1;
    alpha[board[0][0] - 'A'] = 1;
    dfs(0,0,1);
    printf("%d",max);
    return 0;
}

void dfs(int x, int y, int count)
{
    int cur_x = x;
    int cur_y = y;
    for(int i=0;i<4;i++)
    {
        x = x+dx[i];
        y = y+dy[i];// 이미 지나온 경로, 알파벳 중복 체크
        if(x<0 || y<0 || x>=max_x ||y>=max_y||visit[y][x] == 1 ||alpha[board[y][x] - 'A'] == 1)
        {                                // 더 이상 진행 불가하면 지나온 길 값 갱신
            if(max < count)
                max = count;
        }
        else
        {
            visit[y][x] = 1;
            alpha[board[y][x]-'A'] = 1;
            dfs(x,y,count+1);
        }
    }
    visit[cur_y][cur_x] = 0; // 방문전 상태로 되돌리기.
    alpha[board[cur_y][cur_x] - 'A'] = 0;
    return;
}

seico75 2년 전 3

3 4
ABCD
AAAE
IHGF

반례입니다.

36, 37 라인

sc3289 2년 전 0

아니.... 어떻게 이런 짓을........

하..... 감사합니다....

와 진짜 무슨 생각으로 저렇게 짠거지...

이런걸 이틀동안 찾다니 부끄럽네요...

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

문제

문제

출처

ICPC

[C언어] 왜틀렸는지 모르겠습니다.. 게시판 반례 다 통과합니다

sc3289 2년 전 0

seico75 2년 전 3

sc3289 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말