[SWEA] 4014.활주로 건설 (java) / 시뮬레이션

@시뮬레이션 / 2h

어렵다는 말을 듣고 풀다가, 오 생각보다 괜찮은데? 라는 생각을 했다.

그러나 착각이었다..ㅎㅎ 생각해야 할게 많아서, 까다로웠다.

깔끔한 문제는 아니라는 생각이 들었다.

 

 

문제 링크

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWIeW7FakkUDFAVH

SW Expert Academy

 

구현 방법

1. 일단 각 줄을 돌면서

   1) 이전 칸과 지금 칸의 값이 다를 경우

   2) 같을 경우

   로 나눈다.

 

2. 이전 칸과 지금 칸의 값이 다른 경우

   1) 내려가는 경사로를 만들 때

   2) 올라가는 경사로를 만들 때

   3) 경사로를 만들 수 없을 때

   로 나눈다.

이때, 내려가는 경사로와 올라가는 경사로를 다른 로직으로 구현해야 한다.

 

3. 내려가는 경사로의 경우, 지금 칸부터 시작해서 경사로를 그릴 길이가 있는지 && 경사로를 그릴 곳의 값이 다 동일한지를 경사로 길이만큼 체크해야 한다.

 

4. 올라가는 경사로의 경우, 지금까지 오면서 일정한 값이 몇칸이나 유지되었는지를 체크하는 sameHeight의 값이 경사로의 길이보다 길거나 같은지를 체크한다.

 

5. 한 줄을 다 돌았을 때, 활주로를 그릴 수 있는지를 체크하는 boolean변수 값을 확인하고 true면 wayCount를 ++ 해 준다.

 

 

구현 포인트

1. 올라가는 경사로를 그릴 때 사용하는 sameHeight의 값 처리가 중요한데

만약 경사로의 길이가 2라면

3

3

3

2

2

2

여기서 j == 3일때 내려가는 두칸짜리 경사로를 그린다.

그리고 나서 경사로의 마지막 칸인 j = 4로 인덱스를 이동시킨다.

그런데 이때 j = 3, j = 4일때의 높이 2는 경사로를 놓은 곳이므로 더이상 높이가 2가 아니게 된다. 즉, 지금 나의 값과 다음 칸의 값이 같을 수 없게 된다.

그러므로 올라가는 경사로를 놓고 나서 그 경사로의 마지막 칸에서는 sameHeight의 값을 0으로 초기화시켜야 한다.

이 부분을 무심코 1로 초기화하면 테케 40개만 맞는다.

 

내려가는 경사로를 놓을 때는, 지금 나의 값도 포함해야 하므로 sameHeight의 값을 1로 초기화해야 한다.

 

 

2. 경사로는 가로 세로 두 방향으로 그릴 수 있으므로 같은 함수를 방향만 다르게 두개씩 구현했다.

이렇게 하면 같은 코드라 해도 가로 세로를 바꾸면서 틀릴 위험도 있고, 생각도 많이 해야해서 복잡해진다.

그래서 애초에 입력받을때 원래 map을 받고, 가로 세로를 바꾼 reverseMap을 하나 더 만든다.

그러면 한개의 함수로 두개의 맵을 한번씩 돌리면 돼서 코드도 훨씬 간단해지고, 짜기도 편하다.

자주 활용하면 좋을 것 같다!

 

 

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

public class Solution_imp {
	
	private static int N, X, wayCount;
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		StringBuilder sb = new StringBuilder();
		
		int T = Integer.parseInt(br.readLine());
		for (int t = 1; t <= T; t++) {
			wayCount = 0;
			
			st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			X = Integer.parseInt(st.nextToken());
			int[][] originalMap = new int[N][N];
			int[][] reverseMap = new int[N][N];
			
			for (int i = 0; i < N; i++) {
				st = new StringTokenizer(br.readLine());
				for (int j = 0; j < N; j++) {
					originalMap[i][j] = Integer.parseInt(st.nextToken());
					reverseMap[j][i] = originalMap[i][j];
				}
			}
			startPoint(originalMap);
			startPoint(reverseMap);
			
			sb.append("#" + t + " " + wayCount + "\n");
		}
		System.out.println(sb);
	}

	private static void startPoint(int[][] map) {
		for (int i = 0; i < N; i++) {
			boolean enable = true;
			int sameHeight = 1;
			for (int j = 1; j < N; j++) {
				
				if (map[i][j - 1] != map[i][j]) {
					//내려감 
					if (map[i][j - 1] == map[i][j] + 1) {
						//경사로 마지막 칸으로 인덱스를 이동시키기 때문에 경사로를 만들면서 지금 칸의 높이가 변하게 되므로 0으로 초기화 해야함! 
						sameHeight = 0;

						if (slopeCheck(map, i, j, map[i][j])) {
							j += X - 1;
						} else {
							enable = false;
							break;
						}

					//올라감 
					} else if (map[i][j - 1] == map[i][j] - 1) {
						//sameHegith >= X 면 올라오는 경사로를 만들 수 있다는 것이므로 별다른 작업 필요 없음
						if (sameHeight < X) {
							enable = false;
							sameHeight = 1;
							break;
						}
						sameHeight = 1;
						
					//경사로로 이을 수 없는 경우 (차이가 1이 아닌 경우) 
					} else {
						enable = false;
						sameHeight = 1;
						break;
					}
					
				} else {	//앞칸과 높이가 같은 경우 
					sameHeight++;
				}
			}
			if (enable) wayCount++;
		}
	}

	//가로가 true, 세로가 false 
	private static boolean slopeCheck(int[][] map, int x, int y, int height) {
		int k = 1;	//초기 경사로 길이는 1 
		while (y + k < N && map[x][y + k] == height && k < X)	//배열 범위 안에서, 주어진 경사로 길이 안에서 그을 수 있는 경사로 길이 체크 
			k++;
	
		if (k == X) return true;
		else return false;
	}
}

 

 

 

아래가 처음 풀었던 코드, 위가 맵 두개 써서 함수 하나로 푼 코드이다.

수월하지는 않았지만 앞서 풀었던 시뮬레이션 문제들 보다는 괜찮았다.

 

끝!