14890번 경사로
난이도
골드 3
문제 설명
https://www.acmicpc.net/problem/14890
문제
예제 입력
6 2
3 3 3 3 3 3
2 3 3 3 3 3
2 2 2 3 2 3
1 1 1 2 2 2
1 1 1 3 3 1
1 1 2 3 3 2
예제 출력
3
요구사항
- N×N 크기의 지도에서 가로, 세로 방향으로 지나갈 수 있는 길의 개수를 찾는 문제
- 길이 될 수 있는 조건은 모든 칸의 높이가 같거나, 높이 차이가 1인 곳에 길이 L인 경사로를 설치할 수 있을 때
- 경사로는 낮은 칸에 놓아야 하며, 겹치거나 범위를 벗어나서는 안 됨.
접근 방식
이 문제는 완전 탐색과 시뮬레이션으로 해결해야 한다.
길은 하나의 행 또는 열로 이루어져 있으므로, 행과 열을 독립적인 1차원 배열로 분리하기 위해 map에다가 저장하는 getRow(), getCol() 함수를 구현하였다.
1차원 배열에 높이 정보를 담은 후 해당 길이 유효한지 판단하기 위해 check()함수를 사용하였다.
경사로는 겹쳐서 높으면 안되는 조건을 만족하기 위해, check() 내부에 boolean[] ch 배열을 초기화하여 경사로 설치 여부를 확인한다.
Math.abs()로 인접한 두 칸의 높이 차이를 확인한 후 차이가 1보다 크다면, 경사로를 놓을 수 없으므로, 즉시 false를 반환하였다.
만약, 높이가 i에서 i+1로 낮아지는 경우, i+1부터 L개의 연속된 이후 칸까지 높이가 변하지 않는지 혹은 이미 경사로가 놓여있는지 확인 후 경사로를 놓고 경사로를 설치했다고 표시하였다. 반대로, 높이가 i에서 i+1로 높아지는 경우, i부터 L개의 연속된 이전 칸까지 위와 같은 조건을 확인 후 경사로를 놓는 방법으로 문제를 접근하였다.
느낀점
복잡한 시뮬레이션 문제를 해결할 때, 전체 규칙을 한번에 적용하려는 것보다 작은 단위로 쪼개어 문제를 해결해 나가는 것이 매우 중요하다고 느꼈다.
첫 시도에서, 이차원 배열을 그대로 사용하여 해결하려고 시도하니, 코드 구현도 복잡해지고 오류가 발생하였다. 하지만, 이 문제는 하나의 행 또는 열을 기준으로 길이 유효한지 판단할 수 있기 때문에, 1차원 배열로 쪼개어 해당 길이 유효한지 판단하여 해결하니 구현도 간단해지고 오류를 막을 수 있었다.
또한, 경사로를 놓을 수 있는 조건이 단순한 높이 차이뿐만 아니라, 이미 경사로를 놓은 위치는 피해야하는 조건도 간과하지 않게 해 주었다.
