등산로 조성
Last updated
Last updated
틀린 이유
단순히 지형 깎는 공사를 하냐 마냐가 포인트가 아니라, 모든 N*N 칸에 대해 , K를 얼마나 깎는지도 생각해줘야한다. 그렇기 때문에 단순히 1차원을 더 늘여서 두가지 값으로 모든 경우의 수를 구할 수 없다. => 모든 좌표에 대해 k=0~k=K를 반복하는 K-for문이 필요하다.
백트랙킹 : BFS 탐색에서 현재 큐 크기만큼 BFS를 반복하도록 구현하면 백트랙킹하여 연산을 조절할 수 있다. => 큐 크기로 연산을 조절하는 것을 이전에 본 기억이 나는데 다시 찾아보니 없다. 그 때 당시에 시뮬레이션해봤을 때, 그 케이스가 아주 적절히 백트랙킹을 했었다.
K 반복문 : 0부터 K-1까지 반복해서 틀림. 문제에서 k는 1보다 작을만큼 깎아도 된다고 했기 때문에, k는 K만큼 깎을 수도 있고, 0만큼 깎을 수도 있다. 따라서 모든 경우의수를 구하기 위해 K 반복문은 0부터 K까지 반복하도록 해야한다. =>디버깅도 실력이다. K를 출력해보니 K는 출력되지 않는 것을 알 수 있었다.
방문 체크 => 틀린 원인이 되었다. K, 깎는 위치, BFS 시작 위치, BFS 과정 - 큐에서 꺼내는 요소의 좌표와 dist값 그 때마다 최댓값으로 갱신된 ans를 디버깅을 해보니까 k=1, 깎는 위치(2,3), (2,4)에서 BFS 시작, (0,2,5) 까지는 맞았다. 그런데 (0,2)에서 BFS해서 (1,2)로 진행해야 6이라는 최댓값을 얻을 수 있는데 (1,2,4)로 이미 방문했기 때문에 방문한 노드는 다시 방문하지 않기 때문에 6이라는 값을 얻을 수 없게 된 것이다. => 그래서 BFS 정답 코드에는 방문체크하는 부분이 없었던 것이다! => 방문체크하는 부분을 없애줌으로써 테스트 케이스 10개 모두 정답을 도출해낼 수 있었다. 하지만 시간복잡도를 고려해봐야한다. 최악의 경우 시간복잡도를 계산해보면, 1) 모든 칸에 대해서 완전탐색을 한다 : N^2 * N^2 => K값에 따라 완전탐색해야하기 때문에 K * N^2 * N^2이 된다. 2) 최대 높이에서 BFS 한다 => 최대 높이인 칸에서 BFS를 시작한다면 N^2 * N^2가 걸린다. => 최대 높이인칸은 최대 5개이므로 5 * N^2 1과 2의 관계는?곱셈. 왜냐하면1)에서 (K의 값, K만큼 깎는 위치)에 따라 모든 경우에서 각 최대 높이에서 시작하는 BFS를 해야하기 때문이다. 3) ∴ 전체 시간 복잡도 = 1) * 2) = 5 * N^(2+2+2) =>N은 최대 8이므로 5*8^6 = 1310720 < 1억. 이기 때문에 모든 경우를 다 해볼 수 있다. 공간 복잡도 : ? 시간복잡도가 통과되면 공간복잡도도 거의 통과한다고 알고 있음.
정답과의 차이점 : 내 코드에서는 while(!q.isEmpty())에서 int size = q.size(); 바로 밑에 큐에서 요소 꺼내고 ans 갱신하는 것을 구현했는데 정답 코드에서는 큐의 크기만큼 반복하는 for문에서 큐에서 요소를 꺼내는 것을 구현했더라. 결과를 비교해보니 둘다 정답이 올바르게 출력되는 것을 알 수 있었다. 큐의 크기를 갱신해서 큐가 비지 않는 동안 반복하는 반복문이 먼저 존재하고, 큐 크기만큼 반복하는 반복문이 존재한다. 결과적으로 봤을 때, 바깥 반복문 내부에서 큐를 꺼내든, 안쪽 반복문 내부에서 큐를 꺼내든 크게 상관 없는 것 같다.
BFS의 한계
이 문제에서 BFS는 방문체크하지 않고, 인접한 노드들을 모두 방문하기 때문에, 현재의 큐 크기만큼만 반복하는 장치가 있다고 하더라도 매우 비효율적일 것이다. =>DFS로는 어떻게 풀 수 있을까? 재귀함수, 백트랙킹.
DFS로 푼 방법 : 전역변수 ans에 정답을 저장할 것이기 때문에 리턴타입은 void (리턴 타입이 int인 재귀함수 DFS도 구현해볼 법하지만, 귀찮다. 그리고 무엇보다 재귀함수 문제들을 풀어본 결과, 리턴타입이 존재하기보다 계속해서 깊이있기 재귀호출&실행하여 문자열을 만든다거나 하는 경우들이 있었다. 최종 정답을 찾은 경우에 도달했을 때 ,매개변수로 지금까지 만든 문자열들을 컬렉션에 저장한다거나 하는 형태였기 때문에 굳이 리턴 타입이 존재할 필요가 없는 것 같다. 이 문제에서도 최댓값을 찾을 때까지 DFS를 반복하고, 대소 비교를 통해 최댓값을 갱신시켜주기만 하면되고, 이 때 최댓값은 전역변수에 저장하면 된다. 즉, DFS는 최댓값을 찾기 위해 재귀호출&실행만 하면 된다. 뭐라는 거지.. =>암튼 한마디로 리턴 타입이 존재하지 않아도 된다는 것이다~~탐색만 하면 되는 것이다! 1. 불가능한 경우 2. 정답 찾은 경우 3. 다음 경우 호출 : 상하좌우 방향으로 재귀함수 호출&실행
먼저, 위의 3가지 경우로 나눠서 생각해줬다.
불가능한 경우 : 3번을 먼저 생각하고 난 후, 방문체크는 불필요하다고 생각해서 배열 인덱스를 초과하는 경우만 생각해준다. 매개변수로 들어온 (x,y)가 배열범위를 초과할 경우 리턴&종료
정답 찾은 경우 : 출발점, 도착점 이런식으로 종료하는 시점이 정해져있지 않다. 최댓값을 찾을 때까지 계속반복해야하고, 대소비교를 통해 정답ans에 최댓값을 갱신시키는 것이 필요할 뿐이다. 그렇다면 정답을 찾는 경우는 등산로의 길이 최댓값을 찾는 것이고, 등산로의 길이를 계산하는 방법은, 현재 위치에서 다음 위치로 재귀함수를 호출&실행할 때 길이가 1증가하는 것이기 때문에, 재귀함수를 호출&실행할 때 매개변수로 1씩 증가하는 dist를 넘겨줌으로써 계산할 수 있다.
다음 경우를 호출하는 경우 : 제일 먼저 쉽게 생각할 수가 있었는데, 이 때, 이미 방문한 노드를 다시 방문할 수 있는지 생각해봤다. 정답은 다시 방문할 수 있다는 것이다. 1이라는 칸이 있다고 한다면, 9->3->2->1 도 가능하고, 9->6->3->1 도 가능하기 때문이다. 그래도 DFS에서도 BFS처럼 방문체크는 따로 하지 않는다.
맞은 부분
BFS에서 거리는 등산로의 길이를 의미한다.
2중 for문으로 최댓값 찾고, 다시 2중 for문으로 최댓값을 갖는 2차원 배열 좌표를 컬렉션에 넣는다. 이 컬렉션을 순회하면서 각 좌표에서 시작하는 BFS를 한다. 최댓값을 갱신해낸다.
문제 풀이 전략
정체 파악 - 문제 요구 사항 이 문제를 간단히 요약하면 다음과 같다.
가로, 세로가 각각 N인 2차원 배열이 주어졌을 때
가장 높은 지점에 서 출발하여
주변의 낮은 지점으로 등산로를 연결할 때
단 하나의 지점에 대해서만 최대 K높이만큼 지형 깎는 공사가 가능한 경우
가장 긴 등산로의 길이를 구하는 문제
함정 조사 - 주의해야 할 점
등산로 연결 시, 주변 지형 중 작은 높이의 지형만 이어갈 수 있다. => 현재 높이보다 같거나 높은 지형은 등산로 연결X
등산로를 만드는 데 있어 딱 한 지점에 대해서만 최대 K만큼 지형 깎을 수 있음.
현재 지점과 인접해있는 상,하,좌,우 지점만 확인
공사 진행 시, 필요한 경우 높이를 1보다 낮게 만들 수 있다.⭐️⭐️⭐️⭐️⭐️
N은 3~8 사이의 정
K는 1~5 사이의 정수
일부 테스트 케이스만 틀릴 때 생각할 점⭐️
최대 K 깊이만큼 공사를 진행할 수는 있으나, 최대한 길게 등산로를 조성하기 위해서는 K만큼 높이를 다 깎지 않고 높이 값을 (현재 위치의 높이-1)로 만든다. ✅
이미 방문하여 등산로를 조성한 지점은 다시 방문하지 않는다. => 방문 체크 2차원 배열 필요!✅ 8,6,4,3 으로 길이 4인 등산로를 만든 경우, (1,2) 4를 2로 깎아서 (2,2) 1까지 길이 6인 등산로를 만들 수 없다.
전략 수립
1) 대응 방안 구상 - 필요한 이론 2차원 배열로 주어지는 지형을 탐색해서 등산로 만들 수 있는 조건에 부합하는 지점들을 최대한 연결.
재귀함수
2차원 배열 완전 탐색
백트랙킹
이 문제를 혼자 해결하는 데 어려움이 있다면 : SW 문제 해결 기본>미로1 , 미로2 단계적으로 문제를 해결해본다. 미로1 을 풀고 와본다.
