글 읽기 - c 1012 bfs 반례 문의

pinset 2년 전 0

아래 코드 반례 좀 알려주세요..

처음 짜는 코드라 어렵네요..
검색 좀 해 보니 bfs나 dfs는 y 부터 for문을 돌리라고 하던데 그 이유를 아시는 분도 알려주세요.

#include <stdio.h>

#define MAX_LEN 50
#define TRUE 1
#define FALSE 0

typedef struct{
    int x;
    int y;
}Point_T;

int garo_len;
int sero_len;
int bechu_num;
int bechu_loc[MAX_LEN][MAX_LEN] = {0, };
Point_T Queue[MAX_LEN*MAX_LEN];
int res_cnt = 0;
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};
int move_check(int y, int x);
void bfs(int x, int y);
int re_ind=0;

int main()
{
    int num_TC = 0, ind = 0;
    int i = 0, j = 0;
    int bech_x = 0, bech_y = 0;

    scanf("%d", &num_TC);
    
    while(num_TC--)
    { 
        res_cnt = 0;
        scanf("%d %d %d", &garo_len, &sero_len, &bechu_num);
        for(j = 0; j<bechu_num; j++)
        {
            scanf("%d %d",&bech_x, &bech_y); 
            bechu_loc[bech_x][bech_y]=1;
        }
        for (i = 0; i<garo_len; i++)
        {
            for (j = 0; j<sero_len; j++)
            {
                if(bechu_loc[i][j]==1)
                {
                    bfs(i,j);
                    res_cnt++;
                }

            }
        }
        printf("%d\n", res_cnt);

    }
}

void bfs(int x, int y)
{
    int i=0, j =0, idx =0;
    int front = 0, rear = 0;
    int ddx, ddy;
    Point_T pop;

    Queue[rear].x = x;
    Queue[rear].y = y;
    rear++; // enqueue
    while(rear>front)
    {
        pop.x = Queue[front].x;
        pop.y = Queue[front].y;
        front++;  
        for(idx=0; idx<4; idx++)
        {
            ddx = pop.x + dx[idx];
            ddy = pop.y + dy[idx];
            if((move_check(ddx, ddy))==TRUE)
            {
                if (bechu_loc[ddx][ddy]==1)
                {
                    bechu_loc[ddx][ddy]=0;
                    Queue[rear].x = ddx;
                    Queue[rear].y = ddy;
                    rear ++;
                }
                
            }
        }
    }    
}

int move_check(int x, int y)
{
    int ret;
    if((y<0)||(x<0))
        ret = FALSE;
    else if((y>=sero_len)||(x>=garo_len))
        ret = FALSE;
    else
        ret = TRUE;
    return ret;
}

bjh3502 2년 전 0

매 테스트케이스마다 bechu_loc을 전부 0으로 초기화해주세요.

y먼저 for문을 돌린다는 것이 무슨 뜻인지 잘 모르겠습니다만, 행과 열을 착각하지만 않으면

(y, x), (x, y)를 사용하던, 순서는 상관이 없을것으로 보입니다.

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

문제

문제

출처

ICPC

c 1012 bfs 반례 문의

pinset 2년 전 0

bjh3502 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말