글 읽기 - 어디서 시간초과가 발생하는지 잘 모르겠습니다.

powerkim417 3년 전 0

0%에서부터 시간 초과가 발생하였는데, 어느 부분에서 시간 초과가 발생하였는지 잘 모르겠습니다.

예제는 전부 정답이 나오고, 시간 초과가 의심되는 부분이 3개의 while문 또는 재귀라고 생각하여 계속 확인해보았습니다. 그런데 while문도 모두 정상적으로 탈출 조건에 도달하고, 해당 타일에서의 가장 위 또는 아래 말의 번호를 찾는 재귀 부분도 기껏해야 최대 4번밖에 호출되지 않는데 왜 시간초과가 발생하는지 잘 모르겠습니다.

어느 점에서 시간 초과가 발생하는지 답변해주시면 감사하겠습니다!

#include <iostream>
#include <vector>

using namespace std;

int n, k;
int map[12][12];
int dr[4] = {0, 0, -1, 1};
int dc[4] = {1, -1, 0, 0};

bool isRange(int i, int j){
    return (i>=0 && i<n && j>=0 && j<n);
}

int bottom[12][12]; // 비어있으면 -1로 초기화, 있으면 바닥에 있는 말의 번호 저장

struct piece {
    int d;
    int up; // 자신 위 말의 번호. 없을 경우 자신?
    int down; // 자신 아래 말의 번호. 없을 경우 자신?
};

vector<piece> v;

int top(int n){ // n번째 말의 가장 위에 있는 말 번호 반환
    if (v[n].up == n) return n;
    else return top(v[n].up);
}

int bot(int n){ // n번째 말의 가장 아래에 있는 말 번호 반환
    if (v[n].down == n) return n;
    else return bot(v[n].down);
}

pair<int, int> loc(int num){ // num번째 말의 좌표 반환
    for (int i=0 ; i<n ; i++){
        for (int j=0 ; j<n ; j++){
            if (bottom[i][j] == bot(num)) {
                return {i, j};
            }
        }
    }
    return {-1, -1};
}

int main(void){
    cin>>n>>k;
    for (int i=0 ; i<n ; i++){
        for (int j=0 ; j<n ; j++){
            cin>>map[i][j];
            bottom[i][j] = -1;
        }
    }
    int tempr, tempc, tempd;
    for (int i=0 ; i<k ; i++){
        cin>>tempr>>tempc>>tempd;
        bottom[tempr-1][tempc-1] = i; // 첫 입력때 k개의 말 모두 bottom이 된다.
        v.push_back({tempd-1, i, i});
    }

    int time = 1;
    int nr, nc;
    while (1){
        if (time>1000) {
            cout<<"-1";
            return 0;
        }
        bool blue = false;
        // 들어서 -> 뒤집고(red) -> 붙인다
        for (int i=0 ; i<k ; i++){
            pair<int, int> cur = loc(i);
            nr = cur.first + dr[v[i].d];
            nc = cur.second + dc[v[i].d];
            // {nr, nc}: 다음에 이동하는 위치가 아님! 다음에 이동'하려는' 위치! 이렇게 두고 이 위치가 파랑인지 봐야 하는 것
            if (isRange(nr, nc) && map[nr][nc]!=2){ // 흰색 또는 빨간색
                
                // 이동하려는 말의 바닥 여부
                if (v[i].down == i){ // 이동하려는 말이 바닥 말인 경우
                    bottom[cur.first][cur.second] = -1; // 기존 위치는 비게 됨
                }
                else { // 이동하려는 말이 바닥 말이 아닌 경우
                    v[v[i].down].up = v[i].down; // 이동하려는 말 바로 아래가 원래 위치의 가장 위 말이 된다
                }

                int _top=top(i), _cur=i, _temp;
                // 색깔(흰, 빨)에 따른 이동되는 말들 순서 조정
                if (map[nr][nc]==1){ // 빨간색이고, 이동 말이 2개 이상인 경우 현재 위치에서 위치 뒤집기..
                    // 현재 말부터 가장 위 말까지 순서로 위아래 변경
                    while (1){
                        _temp = v[_cur].up;
                        v[_cur].up = v[_cur].down;
                        v[_cur].down = _temp;
                        if (_cur == _top) break;
                        _cur = v[_cur].down; // 다음 말로 이동
                    }

                    // i: 움직이는 스택중 제일 아래였고, 현재는 제일 위
                    // _cur: 움직이는 스택 중 가장 위였고, 현재는 제일 아래
                    if (bottom[cur.first][cur.second] != -1){ // 이동하려는 말이 기존 위치에서 바닥 말이 아니었던 경우
                        v[_cur].up = _cur;
                    }
                }

                // 이동하려는 위치의 비어있음 여부
                if (bottom[nr][nc] == -1){ //새 위치가 비어있었던 경우
                    v[_cur].down = _cur;
                    bottom[nr][nc] = _cur;
                }
                else { // 새 위치에 이미 말이 있는 경우
                    v[_cur].down = top(bottom[nr][nc]); // 이동하는 말의 아래 말 = 새 위치의 가장 위 말
                    v[top(bottom[nr][nc])].up = _cur; // 새 위치의 가장 위 말의 위 말 = 이동하는 말
                }

                // (nr, nc) 말 4개 이상인지 체크
                int cnt = 1;
                int check_cur = bottom[nr][nc];
                while (1){
                    if (check_cur == top(check_cur)) {
                        break;
                    }
                    else {
                        check_cur = v[check_cur].up;
                        cnt++;
                        if (cnt>=4){
                            cout<<time;
                            return 0;
                        }
                    }
                }
                blue = false;
            }
            else { // 파란색 또는 벗어났을 때
                if (blue) { // 이 조건을 두번 들어오면 가만히 있고 다음 말로 넘어감
                    blue = false;
                    continue;
                }
                blue = true;
                // 0<->1 , 2<->3 이 되어야 한다.
                if (v[i].d%2==0) v[i].d++;
                else v[i].d--;
                // 방향을 바꾼 뒤, 같은 i에 대해서 다시 포문을 돌도록 한다.
                i--;
            }
        }
        time++;
    }
}

powerkim417 3년 전 0

100줄에서 _cur를 모두 i로 바꾸고 해결했습니다.

up down 정보가 중간에 꼬이면서 무한루프에 빠진 것 같네요. 읽어주신 분들 모두 감사합니다.

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

문제

문제

출처

ICPC

어디서 시간초과가 발생하는지 잘 모르겠습니다.

powerkim417 3년 전 0

powerkim417 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말