[SWEA] 7396 종구의 딸 이름 짓기

 

메모리와 시간 때문에 많이 틀린 문제다

풀긴했지만 고칠 부분이 많은 코드같다..!

 

우선 문제를 보면 결국 딸 이름은 n+m-1의 길이를 가질것이다

그럼 시작점부터 해서 가중치가 제일 작은것만 골라서 끝점까지 가면 된다!

 

다익스트라! 사용하자

 

각 자리의 알파벳을 가중치라 생각하고 이름을 찾아가다가

n+m-1 길이의 이름을 찾으면 break를하자!

여기서 break안하면 pq에 너무 많이들어가서 메모리가 터진다

 

소스코드

#include <bits/stdc++.h>
using namespace std;
#define ll long long
 
char arr[2001][2001];
bool d[2000][2000];
int t,n,m;
int dx[2] = {1,0};
int dy[2] = {0,1};
bool inner(int x,int y){
    return (0<=x && x<n && 0<=y && y<m);
}
struct node{
    string s;
    int _x,_y;
    node(string s,int x,int y):s(s),_x(x),_y(y){}
};
bool operator<(node a,node b){
    return a.s>b.s;
}
int main(){
    scanf(" %d",&t);
    for(int tc=1;tc<=t;tc++){
        scanf(" %d %d",&n,&m);
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                scanf(" %1c",&arr[i][j]);
                d[i][j]=false;
            }
        }
        string ans="";
        priority_queue<node>pq;
        string start=""; start+=arr[0][0];
        pq.push({node(start,0,0)});
        while(!pq.empty()){
            node p = pq.top(); pq.pop();
            string s = p.s;
            int x = p._x,y=p._y;
 
            if(d[x][y]) continue;
            d[x][y]=true;
            if(s.size()==n+m-1) {
                ans=s; break;
            }
            for(int i=0;i<2;i++){
                int nx = x+dx[i];
                int ny = y+dy[i];
                if(inner(nx,ny) && !d[nx][ny])
                    pq.push(node(s+arr[nx][ny],nx,ny));
            }
        }
        cout<<"#"<<tc<<" "<<ans<<"\n";
    }
}