[JAVA] 백준 14890번 : 경사로 (삼성 SW 역량 테스트 기출 문제)

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

14890번: 경사로

문제

Simulation 문제이다. Queue를 사용하여 구현하다가 올라가는 경사에서 막혀서 다른사람 풀이를 참고하였다.

 

해결 방안

주어진 조건에 맞도록 구현하는 Simulation 문제이다.

1. 각 행과 열마다 지나길 수 있는 길인지 체크해서 갯수를 세준다.
2. 해당 행과 열을 1차원 배열로 만들어서 체크하기 쉽게 만든다. (checkPath()함수)
조건이 맞지 않는 경우 false를 리턴해준다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

// 경사로
public class Main {

	static int N; // 지도 크기 NxN (2~100)
	static int L; // 경사로 길이 (1~N)
	static int[][] map; // 지도
	static boolean[][] visited; // 경사로 놓은지 확인
	static int pathCnt;
	
	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String str;
		str = br.readLine();
		N = Integer.parseInt(str.split(" ")[0]);
		L = Integer.parseInt(str.split(" ")[1]);
		pathCnt = 0;
		
		map = new int[N][N];
		visited = new boolean[N][N];
		
		StringTokenizer st;
		for(int i=0; i<N; i++) {
			str = br.readLine();
			st = new StringTokenizer(str, " ");
			
			for(int j=0; j<N; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		// ===== 입력 끝 =====
		
		// 가능한 길인지 아닌지 체크
		for(int i=0; i<N; i++) {
			if(checkPath(i, 0, true)) // 행
				pathCnt++;
			
			if(checkPath(0, i, false)) // 열
				pathCnt++;
		}
		
		System.out.println(pathCnt);
	}

	// flag: true 행 검사
	// flag: false 열 검사
	static boolean checkPath(int x, int y, boolean flag) {
		
		int[] height = new int[N];
		boolean[] visited = new boolean[N];
		
		for(int i=0; i<N; i++) {
			if(flag)
				height[i] = map[x][i];
			else
				height[i] = map[i][y];
		}
		
		for(int i=0; i<N-1; i++) {
			// 높이가 같을 때
			if(height[i] == height[i+1]) {
				continue;
			}
			// 내려가는 경사
			else if(height[i]-height[i+1] == 1) {
				
				for(int j=i+1; j<=i+L; j++) {
					// 범위 넘어가거나 칸의 높이가 다르거나 이미 경사로가 있는 경우
					if(j>=N || height[i+1]!=height[j] || visited[j]) return false;
					visited[j] = true;
				}
			}
			// 올라가는 경사
			else if(height[i]-height[i+1] == -1) {
				
				for(int j=i; j>i-L; j--) {
					// 범위 넘어가거나 칸의 높이가 다르거나 이미 경사로가 있는 경우
					if(j<0 || height[i]!=height[j] || visited[j]) return false;
					visited[j] = true;
				}
			}
			// 높이가 2칸 이상 차이 날때 (길x)
			else {
				return false;
			}
		}
		
		return true;
	}
	
}