[SW 역량테스트 기출풀이] 백준 14890 - 경사로

* 문제 링크

 

https://www.acmicpc.net/problem/14890

14890번: 경사로

 

* 문제 유형

 

주어진 조건에 맞게 경사로만 설치해주면 되는 전형적인 시뮬레이션

 

* 문제 해설

 

시뮬레이션유형의 문제를 풀 때는 주어진 조건을 꼼꼼하게 읽는 것이 중요하다.

(필자는 꼼꼼하지 못한 탓에 경사로 위에 경사로를 놓으면 안된다는 것을 읽지 못하고 2시간동안 삽질했다.)

 

시간제한은 2초, 지도의 크기는 최대 100X100이고 (1 <= N <= 100)

최소 이어져야하는 L의 범위는 (1<= L <= N) 이므로 100까지 밖에 안된다.

 

따라서 시간복잡도를 고려해보면 극한의 막코딩으로 인해 3중 반복문으로 구현한다고 하더라도

시간복잡도는 O(N^4) 이고 이 경우 최악의 입력을 100으로 가정했을 때 100^4 = 1,000,000이므로 

2초를 넘어가지 않는다. 

 

이 문제를 제외하더라도 지금까지 경험해본 바로는 시뮬레이션에서 시간초과가 나서 통과를 못하는 경우는 없었기에

놓친 부분이 있을 때 수정이 용이하도록 깔끔하게 로직을 구성하는 것이 좋다고 생각한다.

문제에 주어진 조건별 메소드를 따로 설정하는 등과 같이? 

 

아무튼 문제를 요약해보자면 주어진 조건은 다음과 같다.

 

1. 최소 L개의 연속된 칸에 경사로의 바닥이 인접해야한다.

2. 경사로는 높이 차가 1인 경우에만 세울 수 있다.

3. 경사로를 놓은 곳에 또다시 경사로를 놓을 수는 없다.

 

* 풀이 과정

 

check_road 메소드를 통해 경사로를 놓을 수 있는 조건을 판별하였다.

 

디테일한 설명은 아래 코드에 주석으로 달아놓았으며, 주어진 조건에 맞게 구현한 나의 코드는 다음과 같다.

 

import java.util.Scanner;
 
public class Baek_14890_Gold3_경사로 {
	static int N;
	static int L;
	static int[][] map;
	static int cnt = 0;
	static boolean flag;
 
	static boolean check_road(int x, int y, int d) { // x와 y는 map의 인덱스를 전달 받기 위한 파라미터 
													 // d는 0과 1로 나누어 가로와 세로를 나누기 위해 전달받는 파라미터	
				//방문한 위치를 체크해주기 위한 배열
				//경사로를 놓았던 곳에 겹처서 놓을 수 없음
				boolean[] visited = new boolean[N];
				
				// 가로배열의 경우 세로배열의 경우를 나눈다면 2차원 배열이 아닌 1차원 배열만 필요
				int[] height = new int[N];
				
				for(int i = 0; i<N ;i++) { // d가 0이면 가로 1이면 세로
					height[i] = (d==0) ? map[x][y+i] : map[x+i][y];
				}
				
				for(int i = 0 ; i < N-1 ; i++) {
					// 높이가 같으면 경사로를 놓을 필요가 없음
		            if (height[i] == height[i+1]) { // 높이가 같을 경우 모든 조건에 충족하므로 continue
		                continue;
		            }
		            
		            if (Math.abs(height[i] - height[i+1]) > 1) { // 비교하고자 하는 대상과의 차이가 음수일 수도 있고 양수일 수도 있으므로 절댓값을 씌운 값이 1보다 큰 경우 즉시 false 리턴
		            	return false;
		                
		            }
		 
		            // 내리막길 경사로 설치하는 경우
		            if (height[i] - 1 == height[i+1]) { 
		                for (int j=i+1; j<=i+L; j++) { //최소 이어져야하는 갯수만큼 수행
		                    // j가 범위를 벗어나거나 높이가 다르거나 이미 경사로가 있는 경우 경사로를 놓을 수 없음
		                    if (j >= N || height[i+1] != height[j] || visited[j])  { // 1.지도의 범위를 벗어난경우
		                    	return false;										 // 2.땅이 L개만큼 연속되지 않은경우
		                    														 // 3.이미 경사로를 놓은 경우
		                    }
		                    visited[j] = true;
		                    
		                }
		            }
		            // 오르막길 경사로 설치하는 경우
		            else if (height[i] + 1 == height[i+1]) {
		                for (int j=i; j>i-L; j--) { // 최소 이어져야 하는 갯수만큼 수행
		                    if (j < 0 || height[i] != height[j] || visited[j]) { // 조건은 위와 동일
		                    	return false;
		                    	
		                    }
		                    visited[j] = true;
		                       
		                    	
		                    
		                   
		                }
		            }            
		        }
				
		
				return true;
				}
				
				
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		L = sc.nextInt();
		cnt = 0;
		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++) {
			 if(check_road(i,0,0))
				 cnt++;
			 
			 if(check_road(0,i,1))
				 cnt++;
		 }
		
		 
		 System.out.println(cnt);
	}
}
 

 

* 풀이 후기

 

처음엔 단지 2차원 배열로 보고 dfs, bfs로 어찌 풀까 라는 생각을 갖고 접근하여 시간 낭비가 심했다.

저번 포스팅에도 언급하였는데 단순하게 양치기로 쌓인 경험치를 근거로 접근 하는 방식을 고쳐야겠다는 생각을 하였다.

또한, check_road 메소드와 같이 길을 체크하는 부분을 따로 메소드로 구현하지 않고 2중 for문을 두번 방식하는 식으로 막구현 하였었는데 TC의 값에 대한 Solution은 나왔지만 히든 케이스에서 나오지 않는 것을 보고 시뮬레이션의 경우 다시 한번 메소드화 시켜 구현하는 것이 중요하다고 느꼈다.