경사로
Last updated
Last updated
문제를 풀지 못한 이유
2차원 공간에서 행과 열 차원이 혼동되어 열에 대해 연산을 수행하는데 그 열과 겹치는 행도 고려를 해야하는지,경사로를 놓기 위해서는 L개의 동일한 값을 갖는 칸이 필요한데, 문제에서 주어진 예시 지도와 L값으로는 예상 답안의 시뮬레이션이 이해가 가지 않았다. L=2, 2223인데 어떻게 경사로를 놓을 수 있다는 거지..
자연어를 프로그래밍 언어로 바꾸어 사고하는 것이 아직 부족한 듯....
(풀이를 보고 난 후)높이가 1차이 나는 경우에도 현재칸<다음칸, 현재칸>다음칸 2가지 경우로 나눠서 처리를 한다...WOW....정답 코드를 배우는 것이 아니라 프로그래밍적으로 사고하는 방식, 생각하는 힘을 기르는 것이 중요하다...정답 풀이 가이드대로 로직을 생각 따라해보기
구현, 시뮬레이션 문제 푸는 방법 시뮬레이션 해보면서 생각을 확장시켜나간다.
길의 갯수를 구한다. 경사로를 둘 수 있는 곳, 경사로를 둘 수 없는 곳을 판단해서 경사로를 배치하여 길을 만들 수 있다.
경사로를 둘 수 없는 곳 판단 조건을 생각해보고, 경사로를 둘 수 있다면(= 차이가 "1" 난다면) 어떻게 해야하는가? ① 내리막(현재칸 > 다음칸) : 다음칸(i+1)을 기준으로 L개의 연속된 i+1배열값과 동일한 값들이 존재해야한다. ② 오르막(현재칸 < 다음칸) : 현재칸(i)을 기준으로 L개의 연속된 i배열값과 동일한 값들이 존재해야한다.
경사로를 놓을 때는 어떻게 처리할 수 있는가? - boolean 배열 visited을 생성하여 경사로를 놓는 위치에 true로 마킹. 경사로를 놓을 수 있는 위치를 j라고 하면 visited[j]를 true로 마킹함으로써 경사로 놓는 처리를 할 수 있고, visited 배열값이 true인지 확인하여 true라면 이미 경사로가 놓여있는 것이기 때문에 중복되지 않게 경사로를 놓을 수 있다.
솔루션(프로그래밍적 사고하는 방법)
2개의 솔루션을 봤는데 N개의 가로줄과 N개의 세로줄, 총 2N개의 길이 존재할 수 있기 때문에? N번 반복하는 반복문으로 구성했다. => 가로줄 N번, 세로줄 N번 반복해야하는데 일반 2중 for문으로 구성한다면 이 문제에서만큼은 적합하지 않은 반복문이다. 그렇기 때문에 가로줄 N번, 세로줄 N번 따로 해준다. 방향벡터를 설정하여 행인지 열인지 결정하고, 세로줄(열)과 가로줄(행) 각각 N번씩 반복한다.
알고리즘 : 지나갈 수 있는 길 갯수 카운팅 boolean go(x,y,dir) 함수 : 경사로를 놓을 수 있는지 조건 검사한다. 거시적으로 보면, 경사로를 놓지 못하는 경우 false를 리턴하도록해서 필터링하고, 통과된 좌표에 대해서만 true를 리턴하여 true 리턴값을 갖는다면 갯수를 카운팅한다. N개의 행, N개의 열 따로 연산을 처리하기 때문에 행일 때, 열일 때 연산을 구분하기 위해 방향벡터 정수 dir을 매개변수로 넘겨주어 이 방향벡터에 따라 원래의 map데이터에서 적절히 값을 가져와 1차원 배열로 옮겨준다!
경사로 놓을 수 없는 경우 ① 범위 초과 ② 이미 경사로가 있는 경우 ③ 높이 차이가 1이상 나는 경우 ④ 낮은 지점의 칸 높이가 모두 같지 않거나 L개가 연속되지 않는 경우
경사로 놓을 수 있는 경우 : 높이 차이(배열 값) 1 나는 경우, L=4 ① 현재칸(i) > 다음칸(i+1) : 다음칸(i+1)이 더 작다면 경사로를 놓을 칸을 의미하는 변수 j생성, j는 i+1부터 L만큼 1씩 이동하면서 경사로 놓을 수 있는지 조건 판단 후에 경사로 놓는 처리를 한다. ② 현재칸(I) < 다음칸(i+1) : 다음칸(i+1)이 더 크다면 j는 i부터 시작해서 j--로 i부터 L만큼 1씩 감소시키면서 경사로 놓는 처리한다.
조건 판단⭐️⭐️⭐️⭐️⭐️ ① 경사로 놓기 위해 i+1부터 L개 칸 모두 값이 같은지 확인 : j가 이동 반복할 때마다 현재의 j가 경사로 처음 놓는 위치 기준으로 값이 계속 같은지 확인한다! ② 범위 체크 ③ 경사로 중복 체크(boolean 배열 값 확인)
경사로 놓는 처리⭐️⭐️⭐️⭐️⭐️ 경사로 위치 인덱스 j 1씩 증가(감소)시키면서 해당 위치에서 경사로 놓는 조건에 부합한다면 boolean 배열에서 해당하는 j칸에 true로 마킹함으로써 경사로 놓는 처리할 수 있다!
다른 솔루션에서의 Tip 주어진 배열을 NxN으로 연산을 해도 되지만, 아래처럼 배열을 90도 회전시킨 것을 아래로 붙인 배열로 나타내면 가로줄에 대해서만 연산을 수행하며로 구현이 용이해진다고 한다..이 배열을 구현시키는 게 더 어려울 것 같지만..?
실제 구현할 때는 n-1행까지 n*n 배열을 입력받고 난 후, n행부터 아래로 배열값을 채워줘야하기 때문에 반복문을 적절히 구성하여 map[n+x][y] 의 값을 채워줘야 한다.
na982님과 동일하게 아래처럼 2중 반복문을 구성했다.
하지만 우변의 행값j는 감소해야하는 반면, 좌변의 열값j는 증가해야하는 서로 상반되는 양상이다. 동일한 변수 j를 쓰기 때문에 하나의 증가 또는 감소 반복문으로 통일시켜야한다고 생각했지만, na982님 코드에서는 그냥 저렇게 구현되어있었다.
경사로가 오르막이든 내리막이든 뒤집혀도 상관없기 때문이 아닐까 짐작한다.
2번째 풀었을 때 틀린 이유
현재칸, 다음칸 높이 차이(배열 값 차이)가 1보다 크다면 이것은 높이차이가 있음에도 불구하고 경사로를 놓지 못해 결국 지나갈 없는 길이 되 것이 로 continue로 더 반복할 필요 없이 바로 false를 리턴하면 된다!!!!!
마찬가지로, 차이가 1이나서 경사로를 놓을 수 있는 경우에도, 경사로를 놓지 못하는 조건 검사해서 이 중 하나라도 해당이 된다면 1번과 마찬가지인 경우이기 때문에 바로 false를 리턴해야한다!