인프런 커뮤니티 질문&답변

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

1. L의 지점을 조합을 이용해서 시작과 끝점을 vector<vector<int>> landList에 저장해서 완전 탐색 식으로 위치를 바꿔가면서 최단거리를 만들어 봤는데 시간 초과가 났습니다.

   250콤비네이션2이면 괜찮을거 같았는데 뭐가 문제일까요??
   
   2. 치킨배달에 풀이 아이디어를 이용해서 적용했는데 이런식으로 접근 방식도 맞을까요??

    

https://www.acmicpc.net/source/84507554

#include <bits/stdc++.h>
using namespace std;

string s;
int n,m,a[54][54],x,y,ex,ey;
int visited[54][54];
vector<pair<int,int>>land;
vector<vector<int>> landList;
queue<pair<int,int>> q;
vector<pair<int,int>>finish;
 
const int dy[4] = {-1, 0, 1, 0};
const int dx[4] = {0, 1, 0, -1};
int ret = -1;

void combi(int start, vector<int> v){
    if(v.size() == 2){
        landList.push_back(v);
        return;
    }
    for(int i = start + 1; i < land.size(); i++){
        v.push_back(i);
        combi(i,v);
        v.pop_back();
    }
}

int main(){
    cin >> n >> m;
    for(int i =0; i <n;i++){
        cin >> s;
        for(int j=0; j<m;j++){
            if(s[j] == 'L'){
                a[i][j] = 1;
                land.push_back({i,j});
            } 
            if(s[j] == 'W') a[i][j] = 0;
        }
    }
    vector<int> v;
    combi(-1,v);

    for(vector<int> lList : landList){
        fill(&visited[0][0], &visited[0][0] + 54*54, 0);
        for(int ll :lList){
            if(q.size() == 1){
                finish.push_back({land[ll].first, land[ll].second});
            }else{
                visited[land[ll].first][land[ll].second] = 1;
                q.push({land[ll].first, land[ll].second});
            }
            
        }
        
        while(q.size()){
            tie(y,x) = q.front();q.pop();
            for(int i = 0; i < 4; i++){
                int ny = y + dy[i];
                int nx = x + dx[i];
                if(nx < 0 || ny < 0 || ny >= n || nx >= m || !a[ny][nx]) continue;
                if(visited[ny][nx]) continue;
                visited[ny][nx] = visited[y][x] + 1;
                if(visited[finish[0].first][finish[0].second]){
                    ret = max(ret, visited[finish[0].first][finish[0].second]);
                    finish.clear();
                    break;
                }
                q.push({ny,nx});         
            } 
        }
    }

    cout << ret+1 << "\n";
    return 0;

}