풀이
경사로를 배치하여 행이나 열을 처음부터 끝까지 통과가능 여부를 찾는 문제이다.
행과 열을 모두 확인해야하기 때문에 zip() 을 통해 column 들을 row 로 변환시켜 graph 에 extend 해주었다.
각 row 들을 확인하면서 아래 명시된 조건들 중 하나도 부합하지 않을 경우 통과 불가능한 길로 판단하여 False 를 배정한다.
우선 경사로를 배치가능한지 판단하기 위하여,
-
경사로를 이미 배치했었는지
-
경사로를 배치할 공간이 충분한지
-
경사로가 끝나는 지점의 높이가 맞는지
총 세가지의 조건을 걸어 경사로를 통해 올라갈 경우와 내려갈 경우를 나눠서 선언했다.
두 조건 모두 부합하지 않을 경우 바로 지나갈 수 있는지를 판단한 뒤, 그 또한 부합하지 않을 경우 통과 불가능한 길로 판단하여 False 를 배정한다.
이후 isTrue 를 사용해 모든 조건을 배합하여 반복문을 탈출한 경로일 경우 ans += 1 을 해주고 모든 row 에 대한 반복이 끝나면 ans 를 출력해준다.
소스코드
References