글 읽기 - 반례가 뭔지 모르겠습니다. 도와주세요!!

godzilla35 6년 전 0

2차원 배열로 입력받은뒤 차례로 BFS 합니다.

아파트 단지 찾으면 그때부터 네방향으로 큐에 넣으면서 검색합니다.

답이 틀리다고 나오는데... 도와주세요 ㅠㅠ

단순한거라 생각했는데 답이 안나오네요.

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

using namespace std;

typedef struct _NODE
{
int i, j;
}NODE;

int ApartmentN; // 아파트 단지 숫자
int N; // 전체 지도 크기
bool Map[26][26]; // 전체 지도
int ApartmentMap[26][26]; // 아파트 단지 지도
int HouseN[26]; // 단지별 집 숫자 저장 배열

void Solve(int startI, int startJ); 
bool Check(int i, int j); // Map[i][j]에 아파트가 있는지 체크
void PrintApartment(); // Map 출력
bool cmp(int a, int b) { return a<b; } // 정렬을 위한 함수
void Init(); // 초기화
void InputData(); // 데이터 입력 함수

void CheckNode(queue<NODE>& que, int i, int j);

void PrintAnswer();

int main()
{
    Init();

    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= N; j++)
        {
            Solve(i, j);
        }
    }



PrintAnswer();


return 0;
}

void Solve(int startI, int startJ)
{

    if (Map[startI][startJ] == true && ApartmentMap[startI][startJ] == 0)
    {
        ApartmentN++;
        queue<NODE> Queue;

        // 현재 위치 체크
        CheckNode(Queue, startI, startJ);

        while(!Queue.empty())
        {

            NODE Front = Queue.front(); // 큐에 가장 앞에 있는 노드

            // 우
            if (Check(Front.i, Front.j + 1))
            {
                CheckNode(Queue, Front.i, Front.j + 1);
            }

            // 하
            if (Check(Front.i + 1, Front.j))
            {
                CheckNode(Queue, Front.i + 1, Front.j);
            }

            // 좌
            if (Check(Front.i, Front.j - 1))
            {
                CheckNode(Queue, Front.i, Front.j - 1);
            }

            // 상
            if (Check(Front.i - 1, Front.j))
            {
                CheckNode(Queue, Front.i - 1, Front.j);
            }

            Queue.pop(); // 가장 상위 노드 빼버림
        }
    }
}

bool Check(int i, int j)
{
    if (!(i >= 1 && j >= 1 && i <= N && j <= N))
    {
        return false;
    }

    if (ApartmentMap[i][j] == ApartmentN) // 현재 큐에서 체크한 노드
    {
        return false;
    }

    return Map[i][j];
}

void PrintApartment()
{
printf("------------------------- PRINT START ----------------------------------\n");
for (int i = 1; i <= N; i++)
{
for (int j = 1; j <= N; j++)
{
printf("%d", ApartmentMap[i][j]);
}
printf("\n");
}
printf("------------------------- PRINT END ----------------------------------\n");
}

void Init()
{
    N = 0;
    ApartmentN = 0; // 아파트 단지 숫자

    memset(Map, 0, sizeof(Map));
    memset(ApartmentMap, 0, sizeof(ApartmentMap)); // 아파트 지도 초기화
    memset(HouseN, 0, sizeof(HouseN)); // 지도 초기화

    InputData();
}

void InputData()
{
    scanf("%d", &N);
    // 데이터 입력
    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= N; j++)
        {
            scanf("%1d", &Map[i][j]);
        }
    }
}

void CheckNode(queue<NODE>& que, int i, int j)
{
    ApartmentMap[i][j] = ApartmentN; // 지도 표시

    NODE tmp;
    tmp.i = i;
    tmp.j = j;
    que.push(tmp); // 큐에 지금 노드 삽입

    HouseN[ApartmentN]++; // 지금 위치 단지 수 증가시킴
}

void PrintAnswer()
{
    printf("%d\n", ApartmentN); // 단지수

    if (ApartmentN > 0)
    {
    int *parr = new int[ApartmentN];

    for (int i = 0; i < ApartmentN; i++)
    {
        parr[i] = HouseN[i + 1];
    }

    sort(parr, parr + ApartmentN, cmp);

    for (int i = 0; i < ApartmentN; i++)
    {
        printf("%d\n", parr[i]);
    }

    delete[] parr;
    }
}

jh05013 6년 전 0

11
10101010101
01010101010
10101010101
01010101010
10101010101
01010101010
10101010101
01010101010
10101010101
01010101010
10101010101

godzilla35 6년 전 0

올려주신 예제에 답이

61
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1

요거 아닌가요? 제가 문제를 잘못이해하고있는건가...

godzilla35 6년 전 0

아 제가 멍청했네요.. 이해했습니다..

근데 왜 invalid memory exception이 안떳는지 모르겠네요

djm03178 6년 전 1

운영체제는 메모리를 그렇게 칼같이 달라는 만큼만 할당해주지 않습니다. 일정량 할당해놓고 부족해지기 전까지는 그 내부에서 주소값만 가져다 씁니다. 그래서 살짝 인덱스가 벗어나는 정도로 보통은 바로 segmentation fault가 되지는 않습니다.

그보다 문제가 될 가능성이 큰 건, 변수들이 보통 연속된 주소에 할당되기 때문에 주변의 다른 변수의 값을 건드릴 가능성이 크고, 이 때문에 예기치 못한 동작을 하게 됩니다.

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

문제

문제

출처

ICPC

반례가 뭔지 모르겠습니다. 도와주세요!!

godzilla35 6년 전 0

jh05013 6년 전 0

godzilla35 6년 전 0

godzilla35 6년 전 0

djm03178 6년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말