• 카테고리

    질문 & 답변
  • 세부 분야

    알고리즘 · 자료구조

  • 해결 여부

    미해결

3-K 시간초과 & 학습 방법 고민있어요

24.02.16 20:00 작성 24.02.17 19:26 수정 조회수 248

0

- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요!
- 먼저 유사한 질문이 있었는지 검색해보세요.
- 서로 예의를 지키며 존중하는 문화를 만들어가요.
- 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요.

 

안녕하세요. 강의 잘 듣고 있습니다.

  1. 강의를 참고하여 풀었는데. 시간초과가 뜹니다

#include <bits/stdc++.h>

using namespace std;

int R, C;
vector<vector<char>> lake;
queue<vector<int>> candidates_Swan, candidates_SwanTemp;
queue<vector<int>> candidates_Water, candidates_WaterTemp;
vector<vector<int>> delta = {{-1,0},{1,0},{0,-1},{0,1}};
vector<vector<int>> visitedSwan, visitedWater;

bool moveSwan(){
    while(candidates_Swan.size()){

        vector<int> now = candidates_Swan.front(); candidates_Swan.pop();

        for(auto d : delta){
            int next_i = now[0]+d[0];
            int next_j = now[1]+d[1];

            if (next_i >= 0 && next_j >= 0 && next_i < R && next_j < C){

                if (visitedSwan[next_i][next_j] == 0){
                    visitedSwan[next_i][next_j] = 1;
                    if (lake[next_i][next_j] == '.'){
                        candidates_Swan.push({next_i, next_j});
                    }
                    else if (lake[next_i][next_j] == 'X'){
                        candidates_SwanTemp.push({next_i, next_j});
                    }
                    else if (lake[next_i][next_j] == 'L') return true;
                }
            }
        }
    }

    return false;
}

void waterMelting(){

    while(candidates_Water.size()){
        vector<int> now = candidates_Water.front(); candidates_Water.pop();

        for(auto d : delta){
            int next_i = now[0] + d[0];
            int next_j = now[1] + d[1];

            if (next_i >= 0 && next_j >= 0 && next_i < R && next_j < C){
                
                if (visitedWater[next_i][next_j] == 0){

                    if (lake[next_i][next_j] == 'X'){
                        candidates_WaterTemp.push({next_i, next_j});
                        visitedWater[next_i][next_j] = 1;
                        lake[next_i][next_j] = '.';
                    }
                }
            }
        }
    }

    return;
}


int main(){

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> R >> C;
    lake = vector<vector<char>>(R, vector<char>(C));
    visitedSwan = vector<vector<int>>(R, vector<int>(C,0));
    visitedWater = vector<vector<int>>(R, vector<int>(C,0));

    for(int i = 0 ; i < R ; ++i){
        string s;
        cin >> s;
        for(int j = 0 ; j < C; ++j){
            lake[i][j] = s[j];

            if (lake[i][j] == 'L' && candidates_Swan.empty()){
                candidates_Swan.push({i,j}); // 백조는 한마리 위치에서만 시작
                visitedSwan[i][j] = 1;
            }
            if (lake[i][j] == 'L' || lake[i][j] == '.'){
                candidates_Water.push({i,j});
                visitedWater[i][j] = 1;
            }
        }
    }

    int day = 0;
    while(true){

        if (moveSwan()) break;
        waterMelting();

        // cout << endl;
        // for(auto ll : lake){
        //     for(auto l : ll) cout << l;
        //     cout << endl;
        // }
        // cout << endl;

        candidates_Swan = candidates_SwanTemp;
        candidates_Water = candidates_WaterTemp;
        candidates_WaterTemp = queue<vector<int>>();
        candidates_SwanTemp = queue<vector<int>>();
        day++;
    }

    cout << day << "\n";
    return 0;
} 
  1. 강의를 듣기 전에 먼저 문제를 풀고 강의를 듣는 방식을 고수하고 있는데, 한 문제를 푸는데 점점 시간이 늘어나 두시간 정도를 써야 겨우 한문제를 풀고 있습니다.


    이런 방식을 고수하는것이 좋을지,
    어떻게 해야하나 질문드려요.

 

 

 

감사합니다. ^^

답변 2

·

답변을 작성해보세요.

0

안녕하세요 성욱님 ㅎㅎ

코드에서, vector<int> now; 의 선언을 while 문 밖에 빼면 시간초과가 뜨지 않네요...

>> 이 문제 자체가 시간초과가 좀 타이트해서 그렇습니다. 로직상은 문제 없습니다.

    vector<int> now; // <<<<<<<
    while(candidates_Swan.size()){
        now = candidates_Swan.front(); candidates_Swan.pop();

이부분에 대해 설명을 드리면요. 별차이는 없습니다만...

메모리 할당에서 좀 더 이득이긴 합니다.

첫 번째 코드에서는 now 변수가 while 루프의 각 반복마다 새로 선언되고, 이에 따라 벡터의 메모리 할당과 해제가 반복적으로 이루어집니다.

반면에 두 번째 코드에서는 now 변수가 루프 밖에서 한 번만 선언되고, 루프 내에서 값만 갱신되므로 메모리 할당과 해제가 루프의 반복에 따라 발생하지 않습니다.

이로 인해 두 번째 코드가 메모리 할당과 해제 측면에서 더 효율적일 수 있습니다. 하지만.. 그 차이가 그렇게 크지는 않습니다만.. 이 문제 자체가 시간초과가 너무 타이트해서 이부분 까지도 효율적으로 만들어야 한다고 넘어가시면 될 것 같습니다.

 

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.

 

답변 감사합니다.

본 게시글에 2번 질문도 도움 주실수 있으신가요?

안녕하세요 ㅎㅎ 아 제가 이거 답변을 빼먹었네요 ㅠㅠ

강의를 듣기 전에 먼저 문제를 풀고 강의를 듣는 방식을 고수하고 있는데, 한 문제를 푸는데 점점 시간이 늘어나 두시간 정도를 써야 겨우 한문제를 풀고 있습니다.

>> 1 ~ 2시간은 지극히 정상적입니다. 고수해주세요.

0

코드에서, vector<int> now; 의 선언을 while 문 밖에 빼면 시간초과가 뜨지 않네요...

 

bool moveSwan(){
    vector<int> now; // <<<<<<<
    while(candidates_Swan.size()){
        now = candidates_Swan.front(); candidates_Swan.pop();

void waterMelting(){
    vector<int> now; // <<<<<<<
    while(candidates_Water.size()){
        now = candidates_Water.front(); candidates_Water.pop();
채널톡 아이콘