[BOJ14890] 경사로

문제 : 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();
	}
}