글 읽기 - [뿌요뿌요] bfs 시간초과 질문드립니다!

shinyou1024 5년 전 0

안녕하세요!

게시판에 있는 반례는 다 맞게 나오는데

시간초과가 나오네요..!

그런데 코드를 조금만 수정해도 답이 이상하게 나와서

어느 부분을 수정해야 할지 감이 오지 않아 질문드립니다!

조언부탁드립니다.

#include <iostream>
#include <queue>
#include <string.h>
#include <stack>
using namespace std;
char map[20][20];
int h[8];
int dy[4] = { -1, 1, 0, 0 };
int dx[4] = { 0, 0, -1, 1 };
int chk; //한 턴에서 터졌는지
bool visit[20][20] = { false };
int con = 0;//연쇄의 횟수
queue<pair<int, int> > toDelete; //터질 뿌요의 좌표
stack<pair<int, int> > deleted; //지워진 뿌요의 좌표


// 색일치하는 뿌요찾고, 4개 이상이면 toDelete에 넣어줌
void bfs(int y, int x) {
    
    char C = map[y][x];
    visit[y][x] = true;
    queue<pair<int, int> > q;
    q.push(make_pair(y, x));
    
    bool check[20][20] = { false }; // 한 bfs안에서의 방문기록
    check[y][x] = true;
    
    queue<pair<int, int> > same;
    same.push(make_pair(y, x));
    
    int cnt = 1;
    
    
    
    while (!q.empty()) {
        y = q.front().first;
        x = q.front().second;
        q.pop();
        for (int i = 0; i < 4; i++) {
            
            int ny = y + dy[i];
            int nx = x + dx[i];
            // 범위 벗어날경우
            if (ny < 1 || ny>12 || nx < 1 || ny>12) {
                continue;
            }
            if (check[ny][nx] == false && map[ny][nx] == C) {
                cnt++;
                q.push(make_pair(ny, nx));
                check[ny][nx] = true;
                same.push(make_pair(ny, nx));
            }
        }
        
    }
    if (cnt >= 4) {
        chk++;
        for (int i = 0; i < cnt; i++) {
            int a = same.front().first;
            int b = same.front().second;
            toDelete.push(make_pair(a, b));
            visit[a][b] = true;
            same.pop();
        }
    }
}

// 터트리기 : d로 만듦
void del() {
    while (!toDelete.empty()) {
        int y = toDelete.front().first;
        int x = toDelete.front().second;
        deleted.push(make_pair(y, x));
        map[y][x] = 'd';
        h[x]--;
        toDelete.pop();
    }
}
// 중력 적용
void fall() {
    
    while (!deleted.empty()) {
        int i = deleted.top().first;
        int j = deleted.top().second;
        
        
        if (h[j] == 0) {
            map[i][j] = '.';
        }
        else {
            
            int y = i;
            for (int k = 0; k < h[j]; k++) {
                if(1<=y&&y<=12) {
                    map[y][j] = map[y - 1][j];
                    map[y - 1][j] = '.';
                    y--;
                }
            }
        }
        deleted.pop();
    }
}




int main() {
    memset(h, 0, sizeof(h));
    for (int i = 1; i <= 12; i++) {
        for (int j = 1; j <= 6; j++) {
            cin >> map[i][j];
            if (map[i][j] != '.') {
                h[j]++;
            }
        }
    }
    
    
    
    while (true) {
        for (int i = 12; i >= 1; i--) {
            for (int j = 1; j <= 6; j++) {
                if (map[i][j]=='.') {
                    continue;
                }
                if (visit[i][j] == false) {
                    bfs(i, j);
                }
            }
        }
        
        if(chk>0) {
            chk=0;
            del();
            fall();
            con++;
        }
        else
            break;
        
        
        memset(visit, false, sizeof(visit));
    }
    cout << con;
    return 0;
}

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

문제

문제

출처

ICPC

[뿌요뿌요] bfs 시간초과 질문드립니다!

shinyou1024 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말