글 읽기 - 맞았습니다만...

mossolb 2년 전 0

일단 문제 자체는 맞았는데, visited 배열과 관련해서 질문이 있습니다.

저는 처음에 visited 배열 하나를 전역배열로 사용해서 DFS와 BFS의 방문한 노드를 기록했는데, 이렇게 하니까 오류가 생겨서 visitedDFS, visitedBFS를 따로 만들어서 해결했습니다.

그런데 다른 분들의 코드를 보면 visited 배열 하나만 만들어도 아무 문제 없이 실행이 되더라고요. 그래서 전역 배열을 하나만 선언해도 문제가 없을지, 그렇다면 왜 그럴지 알고 싶습니다.

위에서 말한 오류에 대해 말씀드리면, 첫 번째 예제를 입력 시 DFS는 1 2 4 3으로 잘 출력되지만, BFS는 1만 출력합니다.

#include<stdio.h>
#define MAX_VERTICES 1001
#define TRUE 1
#define FALSE 0
int GRAPH[MAX_VERTICES][MAX_VERTICES] = {0,};
short int visitedDFS[MAX_VERTICES];
short int visitedBFS[MAX_VERTICES];
short int queue[MAX_VERTICES];

void DFS(int V, int N)
{
    visitedDFS[V] = TRUE;
    printf("%d ", V);
    for(int i = 1; i <= N; i++)
    {
        if(GRAPH[V][i] == TRUE && visitedDFS[i] == FALSE)
        {
            DFS(i, N);
        }
    }
}

void BFS(int V, int N)
{
    int front = 0;
    int rear = 0;
    printf("%d ", V);
    queue[++rear] = V;
    visitedBFS[V]= TRUE;
    
    while(front < rear)
    {
        V = queue[++front];
        for(int i = 1; i <= N; i++)
        {
            if(GRAPH[V][i] == TRUE && visitedBFS[i] == FALSE)
            {
                printf("%d ", i);
                queue[++rear] = i;
                visitedBFS[i] = TRUE;
            }
        }
    }
}

int main()
{
    int N = 0;
    int M = 0;
    int V = 0;
    scanf("%d %d %d", &N, &M, &V);
    
    int x = 0;
    int y = 0;
    
    for(int i = 0; i < M; i++)
    {
        scanf("%d %d", &x, &y);
        GRAPH[x][y] = TRUE;
        GRAPH[y][x] = TRUE;
    }
    
    DFS(V, N);
    printf("\n");
    BFS(V, N);
    return 0;
}

pinoco3 2년 전 1

DFS를 실행한 이후 visit 배열을 초기화 해주셔야 합니다.
그렇게하지 않으면 DFS이후 BFS에서 첫번째 노드를 방문한 후 36번줄의 if문을 들어가지 못하게되기 때문입니다.
그리고 현재 코드는 정답 코드로 보이는데 실패한 코드를 올려주시면 원인을 정확하게 답변할 수 있습니다.

mossolb 2년 전 0

답변해주셔서 감사합니다. 아래 코드가 제가 전역배열 하나로 짰던 코드입니다.

그리고 답변 보고 초기화를 한번 해 봤는데 visited[MAX_VERTICES] = {0, };로 초기화했더니, 제 환경에선 error C2059: 구문 오류: '{' 이렇게 나오네요. 혹시 전역선언한 배열은 초기화를 다르게 해야 할까요?

#include <stdio.h>
#define MAX_VERTICES 1001
#define TRUE 1
#define FALSE 0
int GRAPH[MAX_VERTICES][MAX_VERTICES] = {
    0,
};
short int visited[MAX_VERTICES];
short int queue[MAX_VERTICES];

void DFS(int V, int N)
{
    visited[V] = TRUE;
    printf("%d ", V);
    for (int i = 1; i <= N; i++)
    {
        if (GRAPH[V][i] == TRUE && visited[i] == FALSE)
        {
            DFS(i, N);
        }
    }
}

void BFS(int V, int N)
{
    int front = 0;
    int rear = 0;
    printf("%d ", V);
    queue[++rear] = V;
    visited[V] = TRUE;

    while (front < rear)
    {
        V = queue[++front];
        for (int i = 1; i <= N; i++)
        {
            if (GRAPH[V][i] == TRUE && visited[i] == FALSE)
            {
                printf("%d ", i);
                queue[++rear] = i;
                visited[i] = TRUE;
            }
        }
    }
}

int main()
{
    int N = 0;
    int M = 0;
    int V = 0;
    scanf("%d %d %d", &N, &M, &V);

    int x = 0;
    int y = 0;

    for (int i = 0; i < M; i++)
    {
        scanf("%d %d", &x, &y);
        GRAPH[x][y] = TRUE;
        GRAPH[y][x] = TRUE;
    }

    DFS(V, N);
    printf("\n");
    BFS(V, N);
    return 0;
}

mossolb 2년 전 0

그냥 for문으로 0부터 MAX_VERTICES까지 모든 인덱스에 0값 주니까 초기화가 되어서 답이 잘 나오네요. 그런데 왜 {0, };으로는 초기화가 안되었을까요?

kimhs 2년 전 1

{0, };과 같은 형태는 처음에 선언과 동시에 초기화할때만 사용이 가능합니다,

이후에는 반복문을 이용하거나 memset등의 함수를 이용해야 합니다.(c++의 경우 std::fill 등의 함수를 이용할 수도 있습니다)

mossolb 2년 전 0

답변해주신 두분 다 고맙습니다. 덕분에 많이 알아갑니다.

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

문제

문제

출처

ICPC

맞았습니다만...

mossolb 2년 전 0

pinoco3 2년 전 1

mossolb 2년 전 0

mossolb 2년 전 0

kimhs 2년 전 1

mossolb 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말