글 읽기 - [C] BFS로 구현했는데 어떤 부분이 틀린지 모르겠습니다.

vndldyd 3년 전 0

매기자마자 바로 틀렸다고 뜨네요.. 고수님들 어떤게 틀린지 봐주시면 감사하겠습니다.

제가 만든 로직에 대해 말씀드리겠습니다.

bfs로 파이어볼의 위치와 방향, 속도,시간을 갱신해(이전 위치의 map 요소는 전부 0으로 만들어줌) push해주면서 시간이 1 증가 되면 (전부 다 움직임을 한번 마친 상태) 파이어볼이 합쳐진지 확인을 해줍니다. 이때 맵에 파이어볼의 요소들을 넣어주면서 만약 맵에 이미 있으면 이미 파이어볼이 있는 상태이므로 합쳐줍니다. 이렇게 합쳐준 이후에 맨처음(아무것도 없다고 생각하고 들어간 파이어볼)의 큐가 차례가 돌아왔을때 4개의 파이어볼로 분산시켜 큐에 같은 시간대로 담아줍니다(다시 넣어줘야 4개의 파이어볼이 분산되어 큐에 담김!).

이와 같은 로직으로 계속해서 k번 파이어볼의 위치를 수정해나갔습니다.

이 로직에 어떤부분이 잘못됐는지 알 수 있을까요? ㅠㅠ

#include <stdio.h>

typedef struct strs {
    int x, y, m, d, s, times;
}queue_;

int N, M, K; // n은 격자 크기 , m은 파이어볼 갯수 , k는 명령 (타임)
int map[50 + 5][50 + 5][3][2]; // 0은 질량 / 1은 속력( 0은 속력 1은 갯수) / 2는 방향
queue_ queue[2500000 + 10];
int wr, qr;
int xx[] = { 0,1,1,1,0,-1,-1,-1 }; // 방향
int yy[] = { -1,-1,0,1,1,1,0,-1 };
// queue 사이즈 250만+10

void push(int x1, int y1, int m1, int d1, int s1, int times1) {
    queue[wr].x = x1;queue[wr].y = y1;queue[wr].m = m1;queue[wr].s = s1;queue[wr].d = d1;queue[wr].times = times1;
    wr++;
}

queue_ pop() {
    return queue[qr++];
}

void prints() {
    for (int i = 0; i < N; i++)
    {
        for (int j = 0;j < N;j++) {
            printf("m:%d/s:%d/s_c:%d/d:%d    ", map[i][j][0][0], map[i][j][1][0], map[i][j][1][1], map[i][j][2][0]);
        }
        printf("\n");
    }

}

void scans() {
    int nx, ny, nm, nd, ns;
    scanf("%d %d %d", &N, &M, &K);
    for (int i = 0; i < M; i++)
    {
        scanf("%d %d %d %d %d", &ny, &nx, &nm, &ns, &nd);
        push(nx-1, ny-1, nm, nd, ns, 0);
        map[ny - 1][nx - 1][0][0] = nm;
        map[ny - 1][nx - 1][1][0] = ns;
        map[ny - 1][nx - 1][2][0] = nd;
    }
    //prints();
    //printf("\n");
}

int BFS() {
    queue_ temp;
    int nx, ny,cnt,remain,remain_s;
    int a_time=1;
    while (wr!=qr)
    {
        temp = pop();
        if (a_time == temp.times) {
            cnt = wr - qr + 1;
            for (int i = 1; i <= cnt; i++)
            {
                if (map[temp.y][temp.x][0][0] == 0) {
                    map[temp.y][temp.x][0][0] = temp.m;
                    map[temp.y][temp.x][1][0] = temp.s;
                    map[temp.y][temp.x][1][1] = 1;
                    map[temp.y][temp.x][2][0] = temp.d % 2; // 홀수면 1 짝수면 0 
                    push(temp.x, temp.y, temp.m, temp.d, temp.s, temp.times);
                }
                else {
                    map[temp.y][temp.x][0][0] += temp.m;
                    map[temp.y][temp.x][1][0] += temp.s;
                    map[temp.y][temp.x][1][1]++;
                    if (map[temp.y][temp.x][2][0] == 1 && temp.d % 2 == 0) {
                        map[temp.y][temp.x][2][0] = 3;
                    }
                    if (map[temp.y][temp.x][2][0] == 0 && temp.d % 2 == 1) {
                        map[temp.y][temp.x][2][0] = 3;
                    }
                }
                if(i != cnt)
                    temp = pop();
            }
            //prints();
            //printf("\n");
            if (a_time == K) {
                int sum=0;
                while (wr != qr)
                {
                    temp = pop();
                    if (map[temp.y][temp.x][0][0] > temp.m) {
                        sum += (map[temp.y][temp.x][0][0] / 5) * 4;
                        continue;
                    }
                    sum += temp.m;
                }
                return sum;
                // k번 명령!
            }
            a_time++;
            continue;
        }
        if (map[temp.y][temp.x][0][0] > temp.m) {
            // 맨처음 들어간거
            // 이걸로 4개로 나눠서 push 해주기
            remain = map[temp.y][temp.x][0][0] / 5;
            if (remain == 0)// 파이어볼의 질량이 0이 되어 다 죽었을 때
                continue;
            remain_s = map[temp.y][temp.x][1][0] / map[temp.y][temp.x][1][1];
            if (map[temp.y][temp.x][2][0] == 3) { // 1,3,5,7
                push(temp.x, temp.y, remain, 1, remain_s, temp.times);
                push(temp.x, temp.y, remain, 3, remain_s, temp.times);
                push(temp.x, temp.y, remain, 5, remain_s, temp.times);
                push(temp.x, temp.y, remain, 7, remain_s, temp.times);
            }
            else {
                push(temp.x, temp.y, remain, 0, remain_s, temp.times);
                push(temp.x, temp.y, remain, 2, remain_s, temp.times);
                push(temp.x, temp.y, remain, 4, remain_s, temp.times);
                push(temp.x, temp.y, remain, 6, remain_s, temp.times);
            }
            map[temp.y][temp.x][0][0] = 0;
            // map[temp.y][temp.x][0]/=5; => 그래야 다음에 pop으로 들어왓을때 한번더 안 나눔! 
            continue;
        }
        map[temp.y][temp.x][0][0] = 0;map[temp.y][temp.x][1][0] = 0;map[temp.y][temp.x][1][1] = 0;map[temp.y][temp.x][2][0] = 0;
        nx = temp.x + xx[temp.d] * temp.s;ny = temp.y + yy[temp.d] * temp.s;
        if (nx < 0) { // 대각선 해도 그런가? => 
            nx = (N - ((-nx) % N));
        }
        if (nx >= N) {
            nx = nx % N;
        }
        if (ny < 0) { // 대각선 해도 그런가? => 
            ny = (N - ((-ny) % N));
        }
        if (ny >= N) {
            ny = ny % N;
        }
        push(nx, ny, temp.m, temp.d, temp.s, temp.times + 1);
    }
    return 0;
}

int main(void) {

    int sol;
    scans();
    sol = BFS();
    printf("%d", sol);
    return 0;
}

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

문제

문제

출처

ICPC

[C] BFS로 구현했는데 어떤 부분이 틀린지 모르겠습니다.

vndldyd 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말