문제 : https://www.acmicpc.net/problem/14890
2중 for문을 사용해서 전체 경로를 일일이 탐색하면서 경사로를 놓을 수 있는지를 판단하는 코드를 작성해야 한다
고려해야 할 점이 많은데, 특히 경사로 길이가 1인 경우를 염두에 두고 반복문 조건을 잘 설정하면 문제는 의외로 쉽게 풀린다
나는 그걸 못해서 좀 삽질을 했지만...ㅠㅡㅠ
푸는 방법은 각 열과 행을 순차적으로 방문하며 경사로를 놓을 수 있는지, 없는지를 판단하는 것
여러가지 경우의 수가 있는데
(1)
3 3 2 2 2 3 이고 경사로 길이가 2라면 건널 수 없다.
3, 3, 2... 순서로 방문하면서 경사로를 둘 수 있으면 두므로 slope배열에는 0, 0, 1, 1, 이 담긴다.
2->3으로 올라가는 경우는 다시 뒤로 돌아가면서 체크를 하는데, 이미 slope[3]이 1이므로 경사로를 또 둘 수 없어서 fail
(2)
3 3 2 3 3 3 인 경우(마찬가지로 경사로길이 = 2)
3 3 2 지점에서 경사로를 둔다(고 가정) slope[2]
경사로는 문제없이 두었으므로 다음으로 진행할텐데, 문제는 경사로 길이가 2이므로 이는 fail case.
따라서 length 를 두어 경사로 길이 조건을 만족하는지 확인했다. 이 경우 length = 1에서 종료되므로 다음으로 진행할 수 없다고 가정함
(3)
3 3 2 2 2 2 는 되는 케이스인데 경사로 길이가 2인 경우 어디까지 점프해야 하는지를 고려해야된다
3 3 2 2 1 1 이라는 케이스를 고려해 보면 3번째 인덱스에서 시작할 때 코드가 꼬이지 않기 때문에, j = L - 1로 설정.
3 3 2 2 2 3 때문에 좀 어려웠던 걸 빼면 무난무난한 문제였던 것 같다(어제 푼 구슬탈출2에 비하면 천국)
DFS나 BFS같은 알고리즘이 생각이 안 나서 결국 for문으로 풀었는데, 뭐 특별한 방법이 있는 것 같진 않다(질문 읽어보니 다들 비슷하게 하신것 같구)
package samsung;
import java.util.Scanner;
import java.lang.Math;
public class Num14890 {
static int[][] map;
static void printMap(int N, int x, int y){
for (int i = 0 ; i < N ; i++){
for(int j = 0 ; j < N ; j++){
if(i != x || y != j){
System.out.print(map[i][j]);
System.out.print(" ");
}
else System.out.print("* ");
}
System.out.println();
}
System.out.println();
}
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int L = sc.nextInt();
map = new int[N][N];
for(int i = 0 ; i= L){
step += (L);
j += (L-1);
continue;
}
else break;
}
else if(map[i][j] - map[i][j+1] == -1){
// 4445
//5434
int length = 0;
for(int k = j ; 0 <= k && length < L ; k--){
if(map[i][k] - map[i][j+1] == -1){
if(slope[k] == 1) {break;}
length++;
slope[k] = 1;
}
else break;
}
if(length >= L){
step += 1;
continue;
}
else break;
}
else break;
}
if(step == N){
answer += 1;
}
}
for(int i = 0 ; i= L){
step += (L);
j += (L-1);
continue;
}
else{
break;
}
}else if(map[j][i] - map[j+1][i] == -1){
int length = 0;
for(int k = j ; 0 <= k && length < L ; k--){
if(map[k][i] - map[j+1][i] == -1 &&slope[k] == 0){
length++;
slope[k] = 1;
}
else{
break;
}
}
if(length >= L){
step += 1;
continue;
}
else{
break;
}
}
else{ break; }
}
if(step == N){
answer += 1;
}
}
System.out.println(answer);
sc.close();
}
}