[ SWEA ] 1949. [모의 SW 역량테스트] 등산로 조성 JAVA 문제풀이

풀이

 

 

이 문제는 DFS를 이용하여 풀이하였습니다.

 

1. 입력을 받을 때 봉우리의 높이를 알아야 하므로 max 변수를 이용하여 봉우리의 위치를 찾아주었습니다.

 

2. 문제에서 등산로는 가장 높은 봉우리에서 시작한다고 하였으므로 ArrayList를 이용하여

시작점이 될 수 있는 봉우리의 위치를 start 리스트에 저장해주었습니다.

 

3. start 리스트에 있는 사이즈만큼 각 봉우리의 위치에서 DFS를 실행하였습니다.

이때, 인자로는 ( i, j, 지형을 깎을 수 있는지 여부, 현재까지 등산로의 길이, 현재 높이 )로 설정해주었습니다.

 

4. 이후 dfs 함수에서 공사를 진행할 기회가 남아 있을 때 ( cut == 1 )와

   더 이상 공사를 진행할 수 없을 때 ( cut == 0 ) 으로 나누어주었습니다.

 

5. DFS 이므로 4방향 탐색이 끝난 후에는 현재의 위치 visited[i][j] 는 다시 false로 설정해주어야

  다른 지점에 방문했다가 방문할 수 있는 경우에도 정답을 찾을 수 있으니 주의하시기 바랍니다.

 

 

 

 

 

코드

 

 

 

 

 

 

 

 

 

 

 

출처

 

 

https://swexpertacademy.com/main/learn/course/lectureProblemViewer.do

SW Expert Academy