[JAVA] 백준 1245 - 농장 관리

문제

1245번: 농장 관리

[ 문제 조건 ]

• 인접한 격자 8개를 모두 비교할 dx, dy 배열
• 산봉우리 높이 > 산봉우리 인접한 격자의 높이
• 산봉우리 총 갯수 = count
• 해당 값이 산봉우리 인지 아닌지 여부 = top

[ 해결순서 ]

1. 문제에서의 '인접하다' 정의를 먼저 이해해야한다. X, Y 좌표 차이가 1이하인 값인 인접한 값. 대각선 4군데 상하좌우 총 8개의 값을 비교하여 깊이우선탐색을 진행해야한다.
2. 모든 farm 배열을 확인하여 방문하지 않은 값 중 0이 아닌 산봉우리가 될 수 있는 값들을 기준으로 dfs() 를 실행하는데
3. 그 전에, 해당 값이 산봉우리라고 임의로 지정해두고 깊이우선탐색 실행 후에도 해당 값이 제일 높으면 그 때 총 값을 증가시킨다.
4. 기존의 깊이우선탐색을 진행하는 방식처럼 dfs() 메소드를 작성하는데
   1. 기준 값이 인접한 값보다 작으면 즉, 높이가 더 큰 산봉우리가 있다면 그 값은 산봉우리가 될 수 없으므로 재귀적으로 너비우선탐색 할 필요도 없다.
   2. 방문하지 않은 값 중에 높이가 같은 값이 있다면 그 값을 기준으로 너비우선탐색을 실행하여 산봉우리를 찾는다.
5. 최종 총 값을 출력한다.

✏️한줄평

처음에 문제를 잘못 이해해서 산봉우리가 여러개인데 왜 하나로 취급하지? 하는 의문이 들었는데, 그냥 같은 높이의 산봉우리라면 하나의 산봉우리 인 것이다. 뭔가 문제의 조건이 애매하다는 느낌은 나만 드는건가. 조금 헷갈렸다. 조건을 같은 높이라면 하나의 산봉우리로 취급한다는 문장이 있으면 좀 명확할 것 같다는 생각이든다. 기존 깊이우선탐색 문제의 응용버전이다.

---

코드