[BOJ] 14890 경사로

14890번: 경사로

문제

크기가 N×N인 지도가 있다. 지도의 각 칸에는 그 곳의 높이가 적혀져 있다. 

오늘은 이 지도에서 지나갈 수 있는 길이 몇 개 있는지 알아보려고 한다. 길이란 한 행 또는 한 열 전부를 나타내며, 한쪽 끝에서 다른쪽 끝까지 지나가는 것이다. 

다음과 같은 N=6인 경우 지도를 살펴보자.

이때, 길은 총 2N개가 있으며, 아래와 같다.

길을 지나갈 수 있으려면 길에 속한 모든 칸의 높이가 모두 같아야 한다. 또는, 경사로를 놓아서 지나갈 수 있는 길을 만들 수 있다. 경사로는 높이가 항상 1이며, 길이는 L이다. 또, 개수는 매우 많아 부족할 일이 없다. 경사로는 낮은 칸과 높은 칸을 연결하며, 아래와 같은 조건을 만족해야한다.

• 경사로는 낮은 칸에 놓으며, L개의 연속된 칸에 경사로의 바닥이 모두 접해야 한다.
• 낮은 칸과 높은 칸의 높이 차이는 1이어야 한다.
• 경사로를 놓을 낮은 칸의 높이는 모두 같아야 하고, L개의 칸이 연속되어 있어야 한다.

아래와 같은 경우에는 경사로를 놓을 수 없다.

• 경사로를 놓은 곳에 또 경사로를 놓는 경우
• 낮은 칸과 높은 칸의 높이 차이가 1이 아닌 경우
• 낮은 지점의 칸의 높이가 모두 같지 않거나, L개가 연속되지 않은 경우
• 경사로를 놓다가 범위를 벗어나는 경우

L = 2인 경우에 경사로를 놓을 수 있는 경우를 그림으로 나타내면 아래와 같다.

경사로를 놓을 수 없는 경우는 아래와 같다.

위의 그림의 가장 왼쪽부터 1번, 2번, 3번, 4번 예제라고 했을 때, 1번은 높이 차이가 1이 아니라서, 2번은 경사로를 바닥과 접하게 놓지 않아서, 3번은 겹쳐서 놓아서, 4번은 기울이게 놓아서 불가능한 경우이다.

가장 위에 주어진 그림 예의 경우에 지나갈 수 있는 길은 파란색으로, 지나갈 수 없는 길은 빨간색으로 표시되어 있으며, 아래와 같다. 경사로의 길이 L = 2이다.

지도가 주어졌을 때, 지나갈 수 있는 길의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다.

출력

첫째 줄에 지나갈 수 있는 길의 개수를 출력한다.

---

삼성 역량 테스트 기출 문제를 뒤지던 중에 알고리즘 분류가 심플하게 구현만 덜렁있길래 한번 풀어봤다. 실제로 빡구현 문제였다. 어차피 길의 후보가 2N개로 정해져 있고 N이 최대 100이므로 완전 탐색으로 해결해도 무조건 2초 안에 해결된다고 생각했다.

 

처음 풀었을 때는 별거 없다고 생각했지만 생각보다 발생할 수 있는 상황이 많았다. 원래는 한 방향으로만 훑었지만 그렇게 하면 해결이 안 될 것 같아서 양방향으로 바꿨다. 지금 생각해보니 나는 무조건 내려가는 경우만 생각했기 때문에 층이 올라가는 경우를 처리하면 단방향으로만 훑어도 괜찮을 것 같다. 

 

처음에는 함수 하나만 사용해서 수평, 수직 방향을 모두 커버하려고 했었다. 그런데 코드를 작성하다 보니까 자꾸 헷갈려서 둘 중 하나만 해결하는 함수를 만들고 제대로 동작하는지 확인한 이후에 복사해서 방향만 바꿔줬다. 그러다 보니까 수직, 수평 방향 함수가 따로 생겨버렸다. 문제를 다 풀고 나서 다른 사람들의 블로그를 보니까 둘 중 하나만 만들고 배열을 전치해서 다시 재사용하고 있었다. 좋은 아이디어라고 생각해서 나도 코드를 수정했다. 나는 왜 이런 생각을 못 했을까.

 

slope 변수는 경사로가 겹치는 경우를 처리하기 위해서 사용했다.

 

후기)

코드를 쓰면서 나도 헷갈릴 때에는 주석을 적으면 훨씬 덜 헷갈린다. 한방에 슥슥슥 하면 좋겠지만 나는 천천히 주석을 쓰면서 해야겠다...