Gidhub BE Developer

# [SW Expert Academy] 1949. 등산로 조성

2018-04-08
goodGid

## Problem

Problem URL : 등산로 조성

## [1] Answer Code (18. 10. 12)

``````#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#define p pair<int,int>
using namespace std;

int map[8][8];
int v[8][8]; // v is visit
int n,k;
int ans;
int dx[] = {0,1,0,-1};
int dy[] = {1,0,-1,0};
vector<p> peak;

bool isEdge(int x, int y){
if( x < 0 || x >= n || y < 0 || y >= n )
return true;
return false;
}

void dfs(int x, int y, int dept, int a_b){ // a_b is Available Break
if(v[x][y])
return ;

int value = map[x][y];
v[x][y] = 1;
for(int i=0; i<4; i++){
int nx = x + dx[i];
int ny = y + dy[i];

if(isEdge(nx, ny))
continue;

if( value > map[nx][ny] ){
dfs(nx,ny,dept+1,a_b);
}
else if(map[nx][ny] >= value && a_b == 1){ // Break 가능한 상태
if(value > map[nx][ny] - k){
int tmp = map[nx][ny];
map[nx][ny] = value-1;
dfs(nx,ny,dept+1,0);
map[nx][ny] = tmp;
}
}
} // end of for i
v[x][y] = 0;
ans = ans < dept ? dept : ans;
}

int main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);

int TC;
cin >> TC;
for(int tc=1; tc<=TC; tc++){
memset(map,0,sizeof(map));
peak.clear();
ans = -1;
cin >> n >> k;

int high_peak = -1;
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
cin >> map[i][j];
if(high_peak < map[i][j])
high_peak = map[i][j];
}
}

for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
if(high_peak == map[i][j])
peak.push_back(p(i,j));
}
}

for(int i=0; i<peak.size(); i++){
memset(v,0,sizeof(v));
dfs(peak[i].first, peak[i].second, 1, 1);
}

cout << "#" << tc << " " << ans << endl ;
}
return 0;
}
``````

### Review

• TC 9개가 틀렸다.

• peak.clear()를 안해주는 실수를 했다.. (절레절레;;)

## [2] Answer Code (18. 04. 08)

``````
#include<iostream>
#include<cstring>
using namespace std;

int dx[] = { 0,1,0,-1 };
int dy[] = { 1,0,-1,0 };

int map[9][9];
int visit[9][9];
int n,k;
int ans;

void dfs(int x, int y, int prev, int d, bool chk){ // d is depth
ans = ans < d ? d : ans;
visit[x][y] = 1;

for(int i=0; i<4; i++){ // [1]
int nx = x + dx[i];
int ny = y + dy[i];

int now = prev;
int next = map[nx][ny];

// 다음 위치가 map범위 벗어나거나
// 다음 위치를 이미 방문
if( next == 0 || visit[nx][ny])
continue;

if( now > next )
dfs(nx,ny,next, d+1, chk);

if(!chk){
for(int i=1; i<=k; i++)
if ( now > next - i){
dfs(nx, ny, next-i, d+1, true);
}
}
} // End of [1] Loop
visit[x][y] = 0;
}

int main(){
int tc = 10;;
cin >> tc;

for(int i=1; i<=tc; i++){
memset(map, 0, sizeof(map));
memset(visit, 0, sizeof(visit));
ans = 0;
cin >> n >> k;

int _max = -1;
for(int a=1; a<=n; a++)
for(int b=1; b<=n; b++){
scanf("%d",&map[a][b]);
_max = _max < map[a][b] ? map[a][b] : _max;
}

for(int a=1; a<=n; a++)
for(int b=1; b<=n; b++)
if( map[a][b] == _max)
dfs(a,b,map[a][b],1,false);

printf("#%d %d\n",i,ans);
}
return 0;
}

``````

### Review

• Code 리뷰 결과 Changed Code

## [3] Answer Code (18. 04. 08)

``````
#include<iostream>
#include<cstring>
using namespace std;

int dx[] = { 0,1,0,-1 };
int dy[] = { 1,0,-1,0 };

int map[9][9];
int visit[9][9];
int n,k;
int ans;
bool chk;

void dfs(int x, int y, int prev, int d){ // d is depth
if( visit[x][y] )
return ;
ans = ans < d ? d : ans;

if( prev != 0 ) { // [0]
visit[x][y] = 1;
for(int i=0; i<4; i++){ // [1]
int nx = x + dx[i];
int ny = y + dy[i];

int now = prev;
int next = map[nx][ny];

if( now == 0 || next == 0 )
continue;

if( now > next )
dfs(nx,ny,next, d+1);

if(! chk){
for(int i=1; i<=k; i++)
if ( now > next - i){
chk = true;
dfs(nx, ny, next-i, d+1);
chk = false;
}
}

} // End of [1] Loop
visit[x][y] = 0;
} // End of [0] If
}

int main(){
int tc = 10;;
cin >> tc;

for(int i=1; i<=tc; i++){
chk = false;
memset(map, 0, sizeof(map));
memset(visit, 0, sizeof(visit));
ans = 0;
cin >> n >> k;

int _max = -1;
for(int a=1; a<=n; a++)
for(int b=1; b<=n; b++){
scanf("%d",&map[a][b]);
_max = _max < map[a][b] ? map[a][b] : _max;
}

for(int a=1; a<=n; a++)
for(int b=1; b<=n; b++){
if( map[a][b] == _max)
dfs(a,b,map[a][b],1);
}

printf("#%d %d\n",i,ans);
}
return 0;
}

``````