BOJ-14890-경사로

BOJ 14890 경사로

문제출저

풀이

푸는데 약2시간 정도 걸린것 같다. 생각보다 고려해주어야 하는 사항들이 많아서 조금 해맸다.
감사하게도 문제에 경사로를 설치가능한지 불가능한지의 경우를 그림으로 자세히 설명해주었다.

우선 탐색방향을 가로(수평), 세로(수평) 방향으로 나누었다.
그래서 가로 방향을 체크하는 함수를 checkHorizontal()로 만들고, 세로 방향을 체크하는 함수를 checkVertical()로 작성하였다.

이제 지나갈 수 있는 길인지 아닌지를 각 함수에서 확인해주어야한다.
길의 모든 칸이 같은 높이라는것을 확인하는 것은 별로 어렵지 않다.
문제는 경사로를 설치하게 되는 경우이다.
우선 가로방향(수평)으로 왼쪽에서 오른쪽으로 탐색한다고 했을때
3 3 2 2 3 3
을 탐색한다고 해보자.
(결론적으로 저 길은 지나갈 수없는 길이다(경사로가 겹쳐서 설치되기 때문에))
x = 1부터 시작해서 x를 n - 1값까지 증가시키면서 board[y][x]와 board[y][x-1]값이 같지 않을 경우를 찾았다.
값이 같지 않을 경우 경사로를 설치할지 말지의 여부를 체크해주어야하는데, 두가지 케이스를 고려할 수 있다.
1) 3 3 2 처럼 board[y][x - 1]> board[y][x] 인 경우와
2) 2 3 3 처럼 board[y][x - 1] < board[y][x] 인 경우이다.

1)의 케이스인 경우 오른쪽으로 경사로를 지어주어야 하고, 경사로의 범위는 x부터 x-1+length 까지가 될것이다.

2)의 케이스인 경우 왼쪽으로 경사로를 지어주어야 하고, 경사로의 범위는 x-length부터 x-1 까지가 될것이다.

이제 확인해줄 것은 경사로가 겹치는지 아닌지의 여부이다.
n길의의 boolean타입의 chk 배열을 따로 만들어서 경사로가 지어지는 영역을 true값을 넣어주고 만약에 이미 경사로가 지어진 영역이라면(chk[x] == true) 해당 길은 지나갈 수 없는 길로 판단하였다.

경사로가 겹치는 영역을 체크하느라 코드가 복잡해졌는데 조금더 간결하게 작성할 수 있는 방법이 없나 고민해봐야겠다.

소스코드

소스코드