티스토리 뷰

 

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

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

 

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

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

 

다익스트라! 사용하자

 

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

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

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

 

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#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<&& 0<=&& 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";
    }
}
 
 

'알고리즘 > SW Expert Academy' 카테고리의 다른 글

[SWEA] 5215 햄버거 다이어트  (0) 2020.04.23
[SWEA] 7793. 오! 나의 여신님  (0) 2020.03.09
[SWEA] 5684 운동  (0) 2020.03.05
[SWEA] 7988 내전 경기  (0) 2020.03.04
[SWEA] 8275 햄스터  (0) 2020.03.04
댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
TAG
more
«   2024/03   »
1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31
글 보관함