[백준] G3 14890 경사로 (java)

www.acmicpc.net/problem/14890

14890번: 경사로

 

풀이

 

1) 이중포문을 돌면서 N^2 이차원 배열에서 라인을 한줄씩 받아온다.

2) boolean 배열을 새로만든다

3) 라인을 탐색한다

3-1) 만약 단차가 생긴다? -> 일단 단차가 2 이상이면 바로 continue

3-2) 그렇지 않다면 경사로를 설치할것이다.

3-3) 내려가는 단차일 경우 : i+1 부터 i+1+L 까지 검사해서 범위 밖이거나, 하나라도 map[i+1] 과 다르다면 continue. 그렇지 않다면 boolean[] = true;

3-4) 올라가는 단차일 경우 3-3과 동일하지만 방향만 반대로 탐색하되 3-3에서 설정한 boolean 값을 잘 파악해야한다.

4) continue에 거치지 않았다면 answer++

5) answer 출력

 

주의사항

 

1) boolean 체크

 

package com.baekJoon;

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

public class BJ_G3_14890_경사로 {
	static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer tokens;
	static int N, L, map[][];
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		input = new BufferedReader(new StringReader(src));
		tokens = new StringTokenizer(input.readLine());
		N = Integer.parseInt(tokens.nextToken());
		L = Integer.parseInt(tokens.nextToken());
		map = new int[N][N];
		
		for(int r=0; r<N; r++) {
			tokens = new StringTokenizer(input.readLine());
			for(int c=0; c<N; c++) {
				map[r][c] = Integer.parseInt(tokens.nextToken());
			}	
		}
		int answer = 0;
		outer : for(int r=0; r<N; r++) {
			int [] line = new int[N];
			boolean [] flag = new boolean[N];
			for(int c=0; c<N; c++) {
				line[c] = map[r][c];
			}
			
			for(int i=0; i<N-1; i++) {
				if(Math.abs(line[i]-line[i+1]) > 1) { 
					continue outer;
				}else {
					if(line[i]-line[i+1] == 1) { // 번개모양
						int layer = line[i+1];
						for(int d=1; d<=L; d++) {
							int ni = i+d;
							if(isIn(ni)) {
								if(line[ni] != layer) {
									continue outer;
								}
							}else {
								continue outer;
							}
							flag[ni] = true;
						}
					}
				}
			}
			
			for(int i=N-1; i>0; i--) {
				if(line[i]-line[i-1] == 1) { // 번개모양
					int layer = line[i-1];
					for(int d=1; d<=L; d++) {
						int ni = i-d;
						if(isIn(ni) && !flag[ni]) {
							if(line[ni] != layer) {
								continue outer;
							}
						}else {
							continue outer;
						}
					}
				}
			}
			answer++;
		}
		
		outer : for(int c=0; c<N; c++) {
			int [] line = new int[N];
			boolean [] flag = new boolean[N];
			for(int r=0; r<N; r++) {
				line[r] = map[r][c];
			}
			for(int i=0; i<N-1; i++) {
				if(Math.abs(line[i]-line[i+1]) > 1) { 
					continue outer;
				}else {
					if(line[i]-line[i+1] == 1) { // 번개모양
						int layer = line[i+1];
						for(int d=1; d<=L; d++) {
							int ni = i+d;
							if(isIn(ni)) {
								if(line[ni] != layer) {
									continue outer;
								}
							}else {
								continue outer;
							}
							flag[ni] = true;
						}
					}
				}
			}
			
			for(int i=N-1; i>0; i--) {
				if(line[i]-line[i-1] == 1) { // 번개모양
					int layer = line[i-1];
					for(int d=1; d<=L; d++) {
						int ni = i-d;
						if(isIn(ni) && !flag[ni]) {
							if(line[ni] != layer) {
								continue outer;
							}
						}else {
							continue outer;
						}
					}
				}
			}
			answer++;
		}
		System.out.println(answer);
	}
	
	static boolean isIn(int n) {
		return (n>=0 && n<N);
	}
	
	static String src =
			"6 1\r\n" + 
			"3 2 1 1 2 3\r\n" + 
			"3 2 2 1 2 3\r\n" + 
			"3 2 2 2 3 3\r\n" + 
			"3 3 3 3 3 3\r\n" + 
			"3 3 3 3 2 2\r\n" + 
			"3 3 3 3 2 2";
}

 

 

후기

 

뭔가 코드가 난잡하지만 내가 푼 골드3문제 중에 가장 빨리 푼 문제가 아닌가 싶다. 노트에 꼼꼼히 예외 상황을 따지면서 정리를 한 후에 코딩을 시작하니 생각보다 수월하게 풀렸다. 현수의 자신감이 1 상승했다!