[JAVA] 백준 14890 경사로 & SWEA 4014 활주로 건설

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

14890번: 경사로

 

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

SW Expert Academy

 

1. 서론

 

이 둘은 삼성 기출로 출력 형식만 다른 완전히 같은 문제이다. 푸는 방법이야 워낙에 다양하지만 난 그렇게 별다른 알고리즘 기법 없이 순수 구현만으로 풀었다.

 

사실 처음에는 SWEA에서 먼저 풀었는데 테케 10개도 잘 돌고 놓친 포인트도 없는데 테케 50개 중에서 44개만 맞았다고 뜨길래 문제 댓글에 있는 반례를 다 넣어보고 구글링까지 하다가 백준의 경사로와 완전 같은 문제라는 걸 알고 역시나 백준에 입출력 형식만 고쳐서 돌려보니 14%에서 돌연 틀렸습니다를 띄워버렸다. 그래서 난 내가 커버하지 못한 케이스가 있는 줄 알고 백준 게시판에 30개가 넘는 반례를 전부 돌렸으나 전부 통과해서 미칠 뻔했다.

 

https://www.acmicpc.net/board/view/96193

글 읽기 - 게시판 모든 반례 + 만든 반례

나 같은 인간들이 많았는지 이리 수많은 반례가 존재했으나... 다 맞았다고요!!

 

결론을 말하자면 나는 엣지케이스의 시간 초과 문제였던 것 같다. 왜냐하면 break 문 한 줄 넣으니까 양쪽 다 통과했기 때문이다. ㅎㅎ

시간 초과가 아니라 틀렸습니다라고 나오길래 시간 초과를 생각 못했는데.... 그럴 수도 있나 보다^^

 

2. 문제 풀이

 

문제가 되게 어려워 보이는데 어렵게 풀자면 어렵게 풀겠지만 난 아주 간단하고 쉬운 방법으로 풀었다.

온갖 반례와 질문들을 보니 사람들이 착각하는 포인트가 있더라....

 

1. 가로줄, 세로줄 각각 독립적인 활주로로 체크해야 한다.

2. 한 줄에 활주로를 여러 개 놓을 수 있으나 서로 겹치면 놓을 수 없기 때문에 활주로를 한쪽에 놓은 경우 다음 활주로가 그 칸을 사용하지 못한다는 것을 알아야 한다.

3. 층은 무조건 1층 차이

 

나도 처음에는 2번을 떠올리지 못해서 약간 헤매었으나 테케를 보면 금방 2번에 대해 눈치채게 된다.

 

함수를 따로 만들어서 돌렸고 그 함수에는 매개변수를 1차원 배열을 넣어서 보낸다. 이 1차원 함수는 각각 가로줄과 세로줄이 담겨있다.

그 배열을 돌면서 층이 변하는 부분의 index값을 한쌍으로 만들어 list<Point> 배열을 만들었다.

그리고 이 list를 돌면서 index를 이용해 양쪽 중에 어느 쪽에 층이 낮은 곳에 x만큼의 공간이 있는지 체크하고 있으면 cnt+1을 하고 그 부분은 경사로를 더 이상 놓을 수 없게 체크해줬다.

 

3. 코드 설명

 

- 백준 버전

 

import java.awt.Point;
import java.io.*;
import java.util.*;

public class Main {
	
	static int n, x, ans;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
        StringTokenizer st = new StringTokenizer(br.readLine().trim());
			n = Integer.parseInt(st.nextToken());
			x = Integer.parseInt(st.nextToken());
			
			int[][] map = new int[n][n];
			for (int i = 0; i < n; i++) {
				st = new StringTokenizer(br.readLine().trim());
				for (int j = 0; j < n; j++)
					map[i][j] = Integer.parseInt(st.nextToken());
			}
			
			ans = 0;
			//가로
			for (int i = 0; i < n; i++) {
				int[] tmp = new int[n];
				for (int j = 0; j < n; j++)
					tmp[j] = map[i][j];
				calc(tmp);
			}
			
			//세로
			for (int i = 0; i < n; i++) {
				int[] tmp = new int[n];
				for (int j = 0; j < n; j++)
					tmp[j] = map[j][i];
				calc(tmp);
			}
        
	    System.out.println(ans);
	}
	
	public static void calc(int[] a) {
		List<Point> list = new ArrayList<>();
		
		int s = a[0];
		for (int i = 1; i < n; i++) {
			if (s != a[i]) {
				if (Math.abs(s - a[i]) != 1) return;
				list.add(new Point(i - 1, i));
				s = a[i];
			}
			if (i == n - 1 && list.isEmpty()) {
				ans++;
				return;
			}
		}
		
		int[] tmp = new int[n];
		for (int i = 0; i < n; i++) 
			tmp[i] = a[i];
		
		for (int i = 0; i < list.size(); i++) {
			int cnt = 0;
		
			if (a[list.get(i).x] < a[list.get(i).y]) {
				for (int j = list.get(i).x; j >= 0; j--)
					if (tmp[j] == a[list.get(i).x])
						cnt++;
                    else
                        break;
				if (cnt < x)
					return;
				else {
					cnt = x;
					for (int j = list.get(i).x; j >= 0; j--) {
						if (tmp[j] == a[list.get(i).x]) {
							tmp[j] = 0;
							cnt--;
						}
						if (cnt == 0) break;
					}
				}
			}
			else {
				for (int j = list.get(i).y; j < n; j++)
					if (tmp[j] == a[list.get(i).y])
						cnt++;
                    else
                        break;
				if (cnt < x)
					return;
				else {
					cnt = x;
					for (int j = list.get(i).y; j < n; j++) {
						if (tmp[j] == a[list.get(i).y]) {
							tmp[j] = 0;
							cnt--;
						}
						if (cnt == 0) break;
					}
				}
			}
			
			if (i == list.size() - 1) 
				ans++;
		}
	}
}

 

- SWEA 버전

 

import java.awt.Point;
import java.io.*;
import java.util.*;

public class Solution {
	
	static int n, x, ans;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int T = Integer.parseInt(br.readLine());
		
		StringBuilder sb = new StringBuilder();
		for (int q = 1; q <= T; q++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			n = Integer.parseInt(st.nextToken());
			x = Integer.parseInt(st.nextToken());
			
			int[][] map = new int[n][n];
			for (int i = 0; i < n; i++) {
				st = new StringTokenizer(br.readLine());
				for (int j = 0; j < n; j++)
					map[i][j] = Integer.parseInt(st.nextToken());
			}
			
			ans = 0;
			int[] tmp = new int[n]; //배열 한 줄만 따로 탐색
			//가로
			for (int i = 0; i < n; i++) {	
				for (int j = 0; j < n; j++)
					tmp[j] = map[i][j];
				calc(tmp);
			}
			
			//세로
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < n; j++)
					tmp[j] = map[j][i];
				calc(tmp);
			}
			
			sb.append("#" + q + " " + ans + "\n");
		}
		bw.write(sb.toString());
		bw.close(); br.close();
	}
	
	public static void calc(int[] a) {
		List<Point> list = new ArrayList<>();
		
		int s = a[0];
		for (int i = 1; i < n; i++) {
			if (s != a[i]) {//배열 탐색하면서 값이 다르면 앞, 뒤 index리스트에 저장
				if (Math.abs(s - a[i]) != 1) return; // 1차이가 아니면 멈춤
				list.add(new Point(i - 1, i));
				s = a[i];
			}
			if (i == n - 1 && list.isEmpty()) { //리스트가 비어있다면 배열 전체의 값이 전부 같음
				ans++;
				return;
			}
		}
		
		int[] tmp = new int[n];
		for (int i = 0; i < n; i++) 
			tmp[i] = a[i];
		
		for (int i = 0; i < list.size(); i++) {
			int cnt = 0;
		
			if (a[list.get(i).x] < a[list.get(i).y]) { //뒷부분의 층이 더 높은 경우
				for (int j = list.get(i).x; j >= 0; j--)
					if (tmp[j] == a[list.get(i).x])
						cnt++;
					else
						break;
				if (cnt < x)
					return;
				else {
					for (int j = list.get(i).x; j >= 0; j--) {
						if (tmp[j] == a[list.get(i).x]) {
							tmp[j] = 0;//경사로 표시
							cnt--;
						}
						if (cnt == 0) break;
					}
				}
			}
			else { //앞부분의 층이 더 높은 경우
				for (int j = list.get(i).y; j < n; j++)
					if (tmp[j] == a[list.get(i).y])
						cnt++;
					else
						break;
				if (cnt < x)
					return;
				else {
					for (int j = list.get(i).y; j < n; j++) {
						if (tmp[j] == a[list.get(i).y]) {
							tmp[j] = 0; //경사로 표시
							cnt--;
						}
						if (cnt == 0) break;
					}
				}
			}
			
			if (i == list.size() - 1) 
				ans++;
		}
	}
}

 

기본적인 로직은 같기 때문에 둘 중 아무거나 봐도 되지만 혹시나 해서 둘 다 올렸다 ㅎㅎ

 

위에서 말한 것처럼 가로, 세로 돌면서 그 배열을 가지고 함수를 돌린다.

배열을 탐색하며 앞, 뒤 값이 다른 경우 두 쌍을 하나로 묶어 리스트에 넣는다.

와중에 두 값의 차가 1인지 체크하고, 리스트에 아무것도 안 담기는 경우는 배열의 값이 다 같은 것이기 때문에 무조건 ans++ 해준다.

 

그리고 앞부분이 더 높은 층인 곳과 뒷부분이 더 높은 층인 경우가 갈리는데 내용은 같다. 둘 중에 더 층이 낮은 곳을 앞이든 뒤든 탐색하면서 같은 층이 몇 개인지 체크한다. 이때 그 크기가 x보다 크거나 같으면 tmp배열에다가 x 길이만큼 경사로를 설치했다고 표시해준다.

tmp에다 안 하면 로직이 이상하게 돌 수 있기 때문에 따로 표시해줬다. 이렇게 하면 경사로를 중복으로 설치하는 경우를 제외할 수 있다.

 

그러면서 중간에 break, return 되지 않고 리스트를 끝까지 돌렸다면 활주로가 이용 가능하기 때문에 ans++해준다.

 

위에 말했던 break문은 x의 길이를 cnt 해주는 부분이었다. 없어도 잘 도는데 뒤에 가면 시간 초과가 나는 모양이다. break하나로 터질게 막아지다니... 대단하다 정말 큰 교훈,,,

 

되게 간단해 보였는데 이렇게 보니까 또 복잡하구먼,, 괜히 골드 문제가 아니네...