글 읽기 - 1012번 안되는 이유를 모르겠습니다.

qpworj1234 2년 전 0

BFS로 구현하였고 한번 방문한 곳은 전부 1로 뒤집고 이어진 곳이 끝나면 카운트에 1을 더해서 답에 저장하는 알고리즘인데 정답이 안나오는 이유를 모르겠습니다....

(DFS로는 구현성공했습니다. BFS로도 한번 풀어보려고 합니다!)

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

int loca[50][50] = {0,};
int visit[50][50] = {0,};

int queue_N[50];
int queue_M[50];
int go_x[4] = {-1,0,1,0};
int go_y[4] = {0,-1,0,1};

void bfs(int start_N, int start_M) {
    int front = 0, rear = 1, temp_N, temp_M;
    visit[start_N][start_M] = 1;
    queue_N[0] = start_N;
    queue_M[0] = start_M;
    while(front < rear) {
        temp_N = queue_N[front];
        temp_M = queue_M[front];
        front++;
        for(int i = 0 ; i < 4 ; i++) {
            if(loca[temp_N + go_y[i]][temp_M + go_x[i]] == 1 
               && visit[temp_N + go_y[i]][temp_M + go_x[i]] == 0) {
                queue_N[rear] = temp_N + go_y[i];
                queue_M[rear] = temp_M + go_x[i];
                rear++;
                visit[temp_N + go_y[i]][temp_M + go_x[i]] = 1;
            }
        }
    }
}
int main()
{
    int T;
    scanf("%d",&T);
    
    int ans[T];
    for(int i = 0 ; i < T ; i++) {
        memset(loca, 0, sizeof(loca));
        memset(visit, 0, sizeof(visit));
        int M, N, K;
        int count = 0;
        scanf("%d %d %d",&M,&N,&K); // M : 가로, 2번째 / N : 세로, 1번째
        for(int d = 0 ; d < K ; d++) {
            int loc_x, loc_y;
            scanf("%d %d",&loc_x,&loc_y);
            loca[loc_y][loc_x] = 1;
        }
        for(int d = 0 ; d < M ; d++) {
            for(int f = 0 ; f < N ; f++) {
                if(loca[f][d] == 1 && visit[f][d] == 0) {
                    bfs(f,d);
                    count++;
                }
            }
        }
        ans[i] = count;
    }
    for(int i = 0 ; i < T ; i++) {
        printf("%d\n",ans[i]);
    }
}

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

문제

문제

출처

ICPC

1012번 안되는 이유를 모르겠습니다.

qpworj1234 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말