• 카테고리

    질문 & 답변
  • 세부 분야

    알고리즘 · 자료구조

  • 해결 여부

    해결됨

3-D 문제 시간초과

24.02.10 01:08 작성 조회수 200

0

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

 

안녕하세요.

강의 잘 듣고 있습니다.!!

 

 

혼자 풀어보는 중인데, 시간초과가 나서 오랫동안 고민하다 질문드립니다.

 

제 생각에는 Fire를 전파하는 부분에서 비효율이 있는듯한데,

이를 개선할 방법이 딱히 떠오르지 않아서요,

 

질문드립니다. ㅠ

 

#include <bits/stdc++.h>

using namespace std;
int R, C;
vector<vector<char>> maze;
pair<int, int> jihun;
vector<pair<int, int>> fire;
vector<vector<int>> delta = {{0,-1},{1,0},{0,1},{-1,0}};
vector<vector<int>> visited;
set<int> ret;

void dfs(pair<int, int>J, int step){
    step+=1;

    // cout << "DEBUG: " << step << ", (" << J.first <<"," << J.second << ")" << endl;
    // for(int i = 0 ; i < R ; ++i){
    //     for(int j = 0 ; j < C ; ++j){
    //         if (i ==J.first && j == J.second) cout << "J";
    //         else cout << maze[i][j];
    //     }
    //     cout << endl;
    // }
    // cout << endl;
    
    if (J.first == 0 || J.second == 0 || J.first == R-1 || J.second == C-1){
        ret.insert(step);
        return;
    }

    // 1. 맵 업데이트
    int cnt = 0;
    int s = fire.size();
    for(int q = 0 ;  q < s ; ++q ){

        for(int p = 0 ; p < 4 ; ++p){
            int nextF_i = fire[q].first + delta[p][0];
            int nextF_j = fire[q].second+ delta[p][1];

            if (nextF_i >=0 && nextF_j >=0 && nextF_i < R && nextF_j < C){
                if (maze[nextF_i][nextF_j] == '.' || maze[nextF_i][nextF_j] == 'J'){
                    maze[nextF_i][nextF_j] = 'F';
                    fire.push_back({nextF_i, nextF_j});
                    cnt ++;
                }
            }
        }
    }

    // 2. dfs 호출 propagation
    for(auto d : delta){
        int next_i = J.first + d[0];
        int next_j = J.second+ d[1];
        if (next_i >= 0 && next_j >= 0 && next_i < R && next_j < C){
            if (visited[next_i][next_j] == 0 && maze[next_i][next_j] == '.'){
                visited[next_i][next_j] = 1; // 방문 처리
                dfs({next_i, next_j}, step);
                visited[next_i][next_j] = 0; // 방문 원복
            }
        }
    }

    // 3. 맵 원복
    while(cnt>0){
        pair<int, int> b = fire.back();
        fire.pop_back();
        maze[b.first][b.second] = '.';
        cnt--;
    }
}



int main(){
    cin >> R >> C;
    maze = vector<vector<char>>(R, vector<char>(C));
    visited = vector<vector<int>>(R, vector<int>(C, 0));

    string s;
    for(int i = 0 ; i <R ; ++i){
        cin >> s;
        for(int j = 0 ; j < C ; ++j){
            maze[i][j] = s[j];
            if (maze[i][j] == 'J')
                jihun = {i,j};
            else if (maze[i][j] == 'F')
                fire.push_back({i,j});
        } 
    }

    visited[jihun.first][jihun.second] = 1;
    dfs(jihun, 0);

    if (!ret.empty()){
        cout << *ret.begin();
    }
    else
        cout <<"IMPOSSIBLE";

    return 0;
}

답변 2

·

답변을 작성해보세요.

0

안녕하세요 성욱님 ㅎㅎ

 

dfs 여서 틀린 것이 아니고, 불을 매번 지폈던 과정이 시간초과의 원인이었던 것 같습니다.

맞을까요? 감사합니다.

>> 2가지부분이 원인이였는데요.

    if (J.first == 0 || J.second == 0 || J.first == R-1 || J.second == C-1){
        ret.insert(step);
        return;
    }

최단거리로 풀었으면 빨리 종료가 될텐데 해당부분 없이 모든 경우의수를 고려해야한다는점

그리고 말씀하신 것 처럼 불을 매번 지핀것도 원인이였습니다.


최단거리 문제임에도 DFS로 푼 이후

>> 가중치가 같은 그래프내에서는 BFS로 최단거리를 푸셔야 합니다.





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

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

감사합니다.

강사 큰돌 올림.


0

아 게시판에 올라온 반례들은 다 맞았습니다.

최단거리 문제임에도 DFS로 푼 이후, 모든 해에 대해서 최소값을 출력하려고 하니 문제인것일까요? ㅎㅎ;;

근데 worst case에서는 dfs나 bfs나 시간복잡도는 같은 것 아닌가요?

강의를 보고 다시 풀었는데, 확실히 불을 매번 지피고, 원복하는 것 보다는

불이 지나간 시간을 다 기록해둔다음에 통과하게 되는 강의의 코드가 효율적이겟네요.

 

dfs 여서 틀린 것이 아니고, 불을 매번 지폈던 과정이 시간초과의 원인이었던 것 같습니다.

맞을까요? 감사합니다.

채널톡 아이콘