기존에 풀던 코드는 너무 더럽고 디버깅의 지옥에서 벗어나지 못했다...
질문검색에서 너무 깔끔한 코드를 봐서 이 분 코드 보고 공부했다.
나는 언제쯤 이렇게 짤 수 있을까
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 55 56 57 58 59 60 61 62 63 | #include<cstdio> #include<queue> #include<algorithm> using namespace std; int dx[]={0,0,1,-1},dy[]={1,-1,0,0}; struct data{int y,x,wall,cnt;}; //y,x,부신 벽,거리 queue<struct data> q; int arr[1002][1002]; int copy_arr[1002][1002][11]; // y,x,부신 벽의 갯수 int n,m,kv,x,y,cnt,wall,ans=999999999; int bfs(int tot){ while(!q.empty()){ x=q.front().x; y=q.front().y; wall=q.front().wall; // 현재까지 부신 벽의 갯수 cnt=q.front().cnt; // 이동거리 q.pop(); if(y==n && x==m){ if(cnt<ans) ans=cnt; return ans; } for(int k=0; k<4; k++){ int nx=x+dx[k]; int ny=y+dy[k]; if(0<nx && nx<=m && 0<ny && ny<=n){ // 빈 공간이고 아직 방문하지 않았다면 if(arr[ny][nx]==0 && copy_arr[ny][nx][wall]==0){ q.push({ny,nx,wall,cnt+1}); copy_arr[ny][nx][wall]=1; } // 벽이지만 아직 부실 수 있는 벽의 갯수가 남아있으면 방문 else if(wall>0 && copy_arr[ny][nx][wall]==0){ q.push({ny,nx,wall-1,cnt+1}); copy_arr[ny][nx][wall]=1; } } } } return -1; } int main(void){ scanf("%d %d %d", &n, &m, &kv); for(int i=1; i<=n; i++){ for(int j=1; j<=m; j++) scanf("%1d", &arr[i][j]); } q.push({1,1,kv,1}); copy_arr[1][1][kv]=1; printf("%d", bfs(kv)); return 0; } | cs |
'백준 2 > 그래프' 카테고리의 다른 글
| [백준 3055] 탈출 (C++) (0) | 2020.12.08 |
|---|---|
| [백준 5427] 불 (C++/Python) (0) | 2020.12.08 |
| [백준 1865] 웜홀 (0) | 2020.12.08 |
| [백준 11657] 타임머신 (0) | 2020.12.08 |
| [백준 2589] 보물섬 (0) | 2020.12.08 |