본문 바로가기
알고리즘 문제/BOJ

[BOJ][14890] 경사로

by 햄과함께 2020. 11. 6.
320x100

문제 : www.acmicpc.net/problem/14890


구현 문제.

행 탐색시 왼쪽에서 오른쪽. 열 탐색시 위에서 아래로 탐색한다.

탐색 중 이전 배열 값을 before, 현재 탐색 중인 값을 now라 하자. 

let, i = 탐색중인 배열 인덱스
int now = (direction == ROW) ? arr[start][i] : arr[i][start];
int before = (direction == ROW) ? arr[start][i-1] : arr[i-1][start];

now, before 값만 알면 되기 때문에 구현시 탐색하려는 행, 열 값과 행, 열 탐색 방향만 알면 위와 같은 방법으로 알 수 있다.

 

[그림1]

같은 높이를 가진 길이 연속적으로 나오는 수를 cnt라 하자.

[그림1]에서 왼쪽은 before(2) < now(3) 인 경우이다. 이 경우 경사로를 만드는데 before와 같은 높이를 가진 길이 L보다 많이 나왔는지 판단해야 한다. 만약 before 까지의 cnt가 L보다 작다면 지나갈 수 없다. 

오른쪽은 before(3) > now(2), before(2) < now(3) 인 경우를 붙여놓았다. before < now 인 경우 now와 같은 높이를 가진 길의 수를 알아야 하는데 아직 탐색하지 않아 알 수 없다. 따라서 사채를 썼다고 생각하고(빌림) cnt를 -L 로 바꿔준다. 만약 탐색 중에 높이가 바뀔때 cnt가 음수라면 빌린걸 갚지 못했으므로 지나갈 수 없다.

 

높이가 변경될 때 뿐만 아니라 배열이 끝날때 까지도 빌린걸 다 갚지 못했다면 지나갈 수 없다.

추가로 칸의 높이차는 1이어야 하므로 칸의 높이차가 2이상인 경우도 해당 길을 지나갈 수 없다고 판단한다.

 

한 행, 열을 지나갈 수 있는지 확인하는데 O(N)이 소요되고 모든 행, 열을 판단해야 하므로 시간복잡도는 O(2 * N^2)


소스코드 : github.com/fpdjsns/Algorithm/blob/master/BOJ/14890.%20%EA%B2%BD%EC%82%AC%EB%A1%9C.cpp

320x100

'알고리즘 문제 > BOJ' 카테고리의 다른 글

[BOJ][17144] 미세먼지 안녕!  (0) 2020.11.08
[BOJ][16235] 나무 재테크  (0) 2020.11.07
[BOJ][1346] 구슬 탈출 2  (0) 2020.11.01
[BOJ][16236] 아기 상어  (0) 2020.10.31
[BOJ][14888] 연산자 끼워넣기  (0) 2020.10.24

댓글