Step-by-Step
[Java] 백준14890 - 경사로 본문
https://www.acmicpc.net/problem/14890
생각보다 너무 어려웠던..문제.. 생각해야하는 경우가 너무 많다.
일단 행과 열 각각 따로따로 탐색해야 하는데, 좌→우 / 우→좌든 상→하/하→상이든 상관없다.
(어차피 오르막이랑 내리막 조건이 같기 때문)
문제에 나와있는 조건에 맞게 길 탐색만 하면 나머지는 상관없다.
1. 다음칸이 같은 높이면 그냥 전진
2. 다음칸이 1칸 낮은 경우, 다다음칸이 똑같이 1칸 낮은지 확인 후 전진 (내리막 사용가능)
- 이 때, slope를 이미 놨다는 의미로 boolean[][] 2차원 배열의 값을 true로 설정
- 다다음칸이 없거나 다른 값이면 전진 불가 -> false 리턴
3. 다음칸이 1칸 높은 경우, 이전 칸이 현재 칸과 같은 높이인지 확인 후 전진 (오르막 사용 가능)
- 이 때, slope가 이미 놓여있으면(boolean[][] 2차원 배열이 true일 경우) 못 올라감 ! -> false 리턴
대충 이런 식으로 구현해줬다.
오르막이랑 내리막만 잘 신경써주면 될듯!
package BOJ_SS;
import java.util.*;
public class boj14890 {
static int n, l, cnt=0;
static int[][] map;
static boolean[][] hasSlope;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
l = sc.nextInt();
map = new int[n][n];
for(int i=0; i<n; i++)
for(int j=0; j<n; j++)
map[i][j] = sc.nextInt();
for(int i=0; i<n; i++) {
hasSlope = new boolean[n][n];
if(checkPath(0,i))
cnt++;
hasSlope = new boolean[n][n];
if(checkPath(1,i))
cnt++;
}
System.out.println(cnt);
}
public static boolean checkPath(int dir, int i) {
switch(dir) {
//좌->우
case 0:{
int num = map[i][0];
for(int j=1; j<n; j++) {
if(map[i][j]==num)
continue;
//오르막
if(map[i][j]==num+1 && j>=l) {
num = map[i][j];
if(checkUpSlope(dir, num-1, i, j-1))
continue;
return false;
}
//내리막
if(map[i][j]==num-1 && j+l<=n) {
num = map[i][j];
if(checkDownSlope(dir, num, i, j))
continue;
return false;
}
return false;
}
return true;
}
//상->하
case 1:{
int num = map[0][i];
for(int j=1; j<n; j++) {
if(map[j][i]==num)
continue;
//오르막
if(map[j][i]==num+1 && j>=l) {
num = map[j][i];
if(checkUpSlope(dir, num-1, i, j-1))
continue;
return false;
}
//내리막
if(map[j][i]==num-1 && j+l<=n) {
num = map[j][i];
if(checkDownSlope(dir, num, i, j))
continue;
return false;
}
return false;
}
return true;
}
}
return false;
}
public static boolean checkUpSlope(int dir, int num, int i, int idx) {
switch(dir) {
case 0:{
for(int j=idx; j>idx-l; j--) {
if(hasSlope[i][j])
return false;
if(map[i][j]!=num)
return false;
}
for(int j=idx; j>idx-l; j--) {
hasSlope[i][j]=true;
}
return true;
}
case 1:{
for(int j=idx; j>idx-l; j--) {
if(hasSlope[j][i])
return false;
if(map[j][i]!=num)
return false;
}
for(int j=idx; j>idx-l; j--) {
hasSlope[j][i]=true;
}
return true;
}
}
return false;
}
public static boolean checkDownSlope(int dir, int num, int i, int idx) {
switch(dir) {
case 0:{
for(int j=idx; j<idx+l; j++) {
if(hasSlope[i][j])
return false;
if(map[i][j]!=num)
return false;
}
for(int j=idx; j<idx+l; j++) {
hasSlope[i][j]=true;
}
return true;
}
case 1:{
for(int j=idx; j<idx+l; j++) {
if(hasSlope[j][i])
return false;
if(map[j][i]!=num)
return false;
}
for(int j=idx; j<idx+l; j++) {
hasSlope[j][i]=true;
}
return true;
}
}
return false;
}
}
'언어 > JAVA' 카테고리의 다른 글
[Java] 백준15683 - 감시 (0) | 2022.10.20 |
---|---|
[Java] 백준14891 - 톱니바퀴 (0) | 2022.10.20 |
[Java] 백준14889 - 스타트와 링크 (0) | 2022.10.19 |
[Java] 백준14888 - 연산자 끼워넣기 (0) | 2022.10.19 |
[Java] 백준1926 - 그림 (1) | 2022.09.23 |
Comments