글 읽기 - dfs로 풀면 안되는 걸까요??

kioio5 7년 전 0

미련하게도.. dfs로 풀었는데 테스트케이스는 통과하는데 50프로 쯤에서 틀렸다고 나오네요

재귀가 너무 많이 호출되서 스택이 터지는 걸까요????

동작원리는

8 8
BBWBWBWB
BWBWBWBW
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBWBWBW

W는 1 B는 0으로 map배열에 저장됩니다.

이 테스트케이스라면 처음에 main에서 k의 값으로 W와 B를 넣어서 끝점까지 도달합니다.

k=0이라면 첫 점이 블랙이라고 가정하고 시작합니다. 첫점 뺴곤 전부 반대로 되어 있으므로 63개의 점을 전부 색칠해야합니다.

k=1이라면 첫 점이 화이트로 가정하고 첫점 뺴곤 전부 맞기 때문에 첫점만 색칠하면 됩니다. 그래서 1이 리턴됩니다.

그러므로 정답은 1이 나옵니다..

반례 혹은 로직이 잘못되었다면 지적해주시기 바랍니다.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_SIZE 50

int map[MAX_SIZE][MAX_SIZE];
int visit[MAX_SIZE][MAX_SIZE];
int m, n;
int min_value = 0x7fffffff;

int min(int a, int b)
{
    return a > b ? b : a;
}

void input()
{
    int i,j;
    char c;

    scanf("%d %d", &m, &n);
    getchar();

    for(i = 0; i < m; i++)
    {
        for(j = 0; j < n; j++)
        {
            c = getchar();
            if(c == 'W') map[i][j] = 1; //W면 1 B면 0을 저장한다.
            else map[i][j] = 0;
        }
        getchar();
    }

}

void visit_init(int x, int y) //방문 초기화
{
    int i, j;
    for(i = x; i < x + 8; i++)
    {
        for(j = y; j < y + 8; j++)
        {
            visit[i][j] = 0;
        }
    }
}

int dfs(int x, int y, int start, int endX, int endY) //시작x,시작y, start=0 or 1, 끝x,끝y
{

    visit[x][y] = 1; //방문표시

    int i;
    int dx[2] = {0, 1};
    int dy[2] = {1, 0};
    int ret = 0;

    if(start != map[x][y]) ret++; //해당 좌표에 있어야 할 값과 다르면 색칠 + 1

    if(x == endX && y == endY) return ret; //끝점이면 리턴

    for(i = 0; i < 2; i++)
    {
        int x2 = x + dx[i];
        int y2 = y + dy[i];

        if(x2 >= m || y2 >= n || visit[x2][y2] == 1) continue; //방문했거나 범위 넘으면 컨티뉴

        ret += dfs(x2, y2, !start, endX, endY); // 다음 포인트의 값은 현재 값의 역이다.(!start)
    }

    return ret;
}

int main()
{
    input();

    int i, j, k;

    for(i = 0; i <= m - 8; i++)
    {
        for(j = 0; j <= n - 8; j++)
        {
            for(k = 0; k < 2; k++)//시작점을 0으로 했을 때와 1로 했을때..k값은 시작점의 값을 나타냄
            {
                visit_init(i, j); //방문 초기화
                min_value = min(dfs(i, j, k, i + 7, j + 7), min_value); //최소값 판별
            }
        }
    }
    printf("%d\n", min_value);

    return 0;
}

sgchoi5 7년 전 1

가능한 좌표에서 size 크기만큼 최소값을 찾는 완전 탐색으로 해도 풀렸습니다. 현재 최소값보다 크면 탐색을 안하도록 했고요.

로직상에 문제가 있어서 잘못된 결과로 인해 틀렸습니다가 나왔을 겁니다. stack 이 터지면 런타임 에러로 나왔던 걸로..

kioio5 7년 전 0

@sgchoi5 한번해보겟습니다감사합니다^^

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

문제

문제

출처

ICPC

dfs로 풀면 안되는 걸까요??

kioio5 7년 전 0

sgchoi5 7년 전 1

kioio5 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말