[백준] 14890번 : 경사로

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

14890번: 경사로

첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다.

www.acmicpc.net

1. 풀이

길을 지나갈 수 있으려면 길에 속한 모든 칸의 높이가 모두 같아야 한다. 또는 경사로를 놓을 수 있는 조건을 만족해야 한다.

지나갈 수 있는 길의 개수를 구하기 위해서 먼저 행별로 탐색한 후 열별로 탐색한다.

열별로 탐색할 때는 원래 지도의 전치행렬을 만들어서 탐색한다.


      
      
      
    
    
      <java />
    
    private static int n, l;

    public static void main(String[] args) throws IOException {
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	n = Integer.parseInt(st.nextToken());
    	l = 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());
    		}
    	}
    	
    	int cnt = 0;
    	cnt += searchMap(map);
    	
    	// 지도의 전치행렬 생성
    	int[][] transposeMap = new int[n][n];
    	for (int i = 0; i < n; i++) {
    		for (int j = 0; j < n; j++) {
    			transposeMap[i][j] = map[j][i];
    		}
    	}
    	
    	cnt += searchMap(transposeMap);
    	
    	System.out.println(cnt);
    }

int searchMap(int[][] map)

지도를 행별로 탐색하여 지나갈 수 있는 길의 개수를 구한다.

각 행을 탐색할 때 경사로 설치 여부를 저장하는 boolean[] stairs를 생성하고, 경사로를 놓을 수 있는 경우 makeStairs() 메서드를 호출하여 경사로를 놓는다.


      
      
      
    
    
      <java />
    
    private static int searchMap(int[][] map) {
    	int cnt = 0;
    	for (int i = 0; i < n; i++) {
    		int first = map[i][0];
    		boolean flag = true;
    		boolean[] stairs = new boolean[n];
    		
    		for (int j = 1; j < n; j++) {
    			if (first != map[i][j]) { // 경사로에 높이 차가 생기는 경우
    				if (first == map[i][j]+1) {
    					// 범위를 벗어나는 경우
    					if (j + l > n) {
    						flag = false;
        					break;
    					}
    					
    					// L개의 연속된 칸의 높이가 모두 같아야 하며, 이미 계단이 놓여져 있지 않아야 경사로를 놓을 수 있다.
    					// 같지 않거나 계단이 이미 있으면 flag를 false로 변경 후, break
    					int[] copyMap = Arrays.copyOfRange(map[i], j, j+l);
    					boolean[] copyStairs = Arrays.copyOfRange(stairs, j, j+l);
    					if (Arrays.stream(copyMap).distinct().count() != 1 || isStair(copyStairs)) {
    						flag = false;
        					break;
    					}
    					// 경사로를 놓고, first와 j 값 업데이트
    					makeStairs(stairs, j, j+l);
    					first = map[i][j];
    					j = j+l-1;
    				}
    				else if (first + 1 == map[i][j]) {
    					// 범위를 벗어나는 경우
    					if (j - l < 0) {
    						flag = false;
        					break;
    					}
    					
    					// L개의 연속된 칸의 높이가 모두 같아야 하며, 이미 계단이 놓여져 있지 않아야 경사로를 놓을 수 있다.
    					// 같지 않거나 계단이 이미 있으면 flag를 false로 변경 후, break
    					int[] copyMap = Arrays.copyOfRange(map[i], j-l, j);
    					boolean[] copyStairs = Arrays.copyOfRange(stairs, j-l, j);
    					if (Arrays.stream(copyMap).distinct().count() != 1 || isStair(copyStairs)) {
    						flag = false;
        					break;
    					}
    					
    					// 경사로를 놓고, first 값 업데이트
    					makeStairs(stairs, j-l, j);
    					first = map[i][j];
    				}
    				else { // 낮은 칸과 높은 칸의 높이 차이가 1이 아닌 경우
    					flag = false;
    					break;
    				}
    			}
    		}
    		
    		if (flag) { // 지나갈 수 있는 길인 경우
    			cnt++;
    		}
    	}
    	
    	return cnt;
    }

boolean isStair(boolean[] stairs)

주어진 stairs 배열에 경사로가 있으면 true를 리턴, 경사로가 없다면 false를 리턴한다.

void makeStairs(boolean[] stairs, int start, int end)

start부터 end-1까지 경사로를 설치한다. 즉, stairs[i]를 true로 변경한다.


      
      
      
    
    
      <java />
    
    private static boolean isStair(boolean[] stairs) {
    	for (int i = 0; i < stairs.length; i++) {
    		if (stairs[i]) {
    			return true;
    		}
    	}
    	return false;
    }
    
    private static void makeStairs(boolean[] stairs, int start, int end) {
    	for (int i = start; i < end; i++) {
    		stairs[i] = true;
    	}
    }

2. 전체 코드


      
      
      
    
    
      <java />
    
import java.io.*;
import java.util.*;

public class Main {
	
	private static int n, l;

    public static void main(String[] args) throws IOException {
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	n = Integer.parseInt(st.nextToken());
    	l = 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());
    		}
    	}
    	
    	int cnt = 0;
    	cnt += searchMap(map);
    	
    	// 지도의 전치행렬 생성
    	int[][] transposeMap = new int[n][n];
    	for (int i = 0; i < n; i++) {
    		for (int j = 0; j < n; j++) {
    			transposeMap[i][j] = map[j][i];
    		}
    	}
    	
    	cnt += searchMap(transposeMap);
    	
    	System.out.println(cnt);
    }
    
    private static int searchMap(int[][] map) {
    	int cnt = 0;
    	for (int i = 0; i < n; i++) {
    		int first = map[i][0];
    		boolean flag = true;
    		boolean[] stairs = new boolean[n];
    		
    		for (int j = 1; j < n; j++) {
    			if (first != map[i][j]) { // 경사로에 높이 차가 생기는 경우
    				if (first == map[i][j]+1) {
    					// 범위를 벗어나는 경우
    					if (j + l > n) {
    						flag = false;
        					break;
    					}
    					
    					// L개의 연속된 칸의 높이가 모두 같아야 하며, 이미 계단이 놓여져 있지 않아야 한다.
    					// 같지 않거나 계단이 이미 있으면 flag를 false로 변경 후, break
    					int[] copyMap = Arrays.copyOfRange(map[i], j, j+l);
    					boolean[] copyStairs = Arrays.copyOfRange(stairs, j, j+l);
    					if (Arrays.stream(copyMap).distinct().count() != 1 || isStair(copyStairs)) {
    						flag = false;
        					break;
    					}
    					// 계단을 세우고, first와 j 값 업데이트
    					makeStairs(stairs, j, j+l);
    					first = map[i][j];
    					j = j+l-1;
    				}
    				else if (first + 1 == map[i][j]) {
    					// 범위를 벗어나는 경우
    					if (j - l < 0) {
    						flag = false;
        					break;
    					}
    					
    					// L개의 연속된 칸의 높이가 모두 같아야 하며, 이미 계단이 놓여져 있지 않아야 한다.
    					// 같지 않거나 계단이 이미 있으면 flag를 false로 변경 후, break
    					int[] copyMap = Arrays.copyOfRange(map[i], j-l, j);
    					boolean[] copyStairs = Arrays.copyOfRange(stairs, j-l, j);
    					if (Arrays.stream(copyMap).distinct().count() != 1 || isStair(copyStairs)) {
    						flag = false;
        					break;
    					}
    					
    					// 계단을 세우고, first 값 업데이트
    					makeStairs(stairs, j-l, j);
    					first = map[i][j];
    				}
    				else { // 낮은 칸과 높은 칸의 높이 차이가 1이 아닌 경우
    					flag = false;
    					break;
    				}
    			}
    		}
    		
    		if (flag) { // 계단을 놓는 경우
    			cnt++;
    		}
    	}
    	
    	return cnt;
    }
    
    private static boolean isStair(boolean[] stairs) {
    	for (int i = 0; i < stairs.length; i++) {
    		if (stairs[i]) {
    			return true;
    		}
    	}
    	return false;
    }
    
    private static void makeStairs(boolean[] stairs, int start, int end) {
    	for (int i = start; i < end; i++) {
    		stairs[i] = true;
    	}
    }
    
}

3. 수정한 풀이

searchMap()을 호출하여 2차원 배열을 인자로 넘기는 대신, 2차원 배열의 한 행을 인자로 넘겨 각 행에 대해 탐색하도록 한다. 메서드 명도 searchMap()에서 searchOneLine()으로 변경했다.


      
      
      
    
    
      <java />
    
import java.io.*;
import java.util.*;

public class Main {
	
	private static int n, l;

    public static void main(String[] args) throws IOException {
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	n = Integer.parseInt(st.nextToken());
    	l = 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());
    		}
    	}
    	
    	// 지도의 전치행렬 생성
    	int[][] transposeMap = new int[n][n];
    	for (int i = 0; i < n; i++) {
    		for (int j = 0; j < n; j++) {
    			transposeMap[i][j] = map[j][i];
    		}
    	}
    	
    	int cnt = 0;
    	
    	for (int i = 0; i < n; i++) {
    		int[] copyMap = Arrays.copyOf(map[i], n);
    		if(searchOneLine(copyMap))
    			cnt++;
    		copyMap = Arrays.copyOf(transposeMap[i], n);
    		if(searchOneLine(copyMap))
    			cnt++;
    	}
    	
    	System.out.println(cnt);
    }
    
    private static boolean searchOneLine(int[] map) {
    	boolean[] stairs = new boolean[n]; // 경사로 설치 여부
    		
    	for (int j = 1; j < n; j++) {
    		int diff = map[j-1] - map[j];
    		
    		if (diff > 1 || diff < -1) return false;
    		
    		if (diff == 1) {
    			// 범위를 벗어나는 경우
    			if (j + l > n) {
    				return false;
    			}
    					
    			// L개의 연속된 칸의 높이가 모두 같아야 하며, 이미 계단이 놓여져 있지 않아야 한다.
    			// 같지 않거나 계단이 이미 있으면 false를 리턴한다.
    			int[] copyMap = Arrays.copyOfRange(map, j, j+l);
    			boolean[] copyStairs = Arrays.copyOfRange(stairs, j, j+l);
    			if (Arrays.stream(copyMap).distinct().count() != 1 || isStair(copyStairs)) {
    				return false;
    			}
    			// 경사로를 놓고, j 값 업데이트
    			makeStairs(stairs, j, j+l);
    			j = j+l-1;
    		}
    		else if (diff == -1) {
    			// 범위를 벗어나는 경우
    			if (j - l < 0) {
    				return false;
    			}
    				
    			// L개의 연속된 칸의 높이가 모두 같아야 하며, 이미 계단이 놓여져 있지 않아야 한다.
    			// 같지 않거나 계단이 이미 있으면 false를 리턴한다.
    			int[] copyMap = Arrays.copyOfRange(map, j-l, j);
    			boolean[] copyStairs = Arrays.copyOfRange(stairs, j-l, j);
    			if (Arrays.stream(copyMap).distinct().count() != 1 || isStair(copyStairs)) {
    				return false;
    			}
    				
    			// 경사로 놓기
    			makeStairs(stairs, j-l, j);
    		}
    	}
    		
    	return true;
    }
    
    private static boolean isStair(boolean[] stairs) {
    	for (int i = 0; i < stairs.length; i++) {
    		if (stairs[i]) {
    			return true;
    		}
    	}
    	return false;
    }
    
    private static void makeStairs(boolean[] stairs, int start, int end) {
    	for (int i = start; i < end; i++) {
    		stairs[i] = true;
    	}
    }
    
}

4. Reference (다른 풀이)

728x90

'Algorithm 문제 풀이 > 백준' 카테고리의 다른 글

[백준] 1325번 : 효율적인 해킹 - 자바[Java] (0)	2023.06.23
[백준] 20055번 : 컨베이어 벨트 위의 로봇 - 자바[Java] (0)	2023.04.04
[백준] 21608번 : 상어 초등학교 - 자바[Java] (0)	2023.03.17
[백준] 14719번 : 빗물 - 자바[Java] (0)	2023.03.16
[백준] 20164번 : 홀수 홀릭 호석 - 자바[Java] (0)	2023.03.16

내 블로그 - 관리자 홈 전환	`Q` `Q`
새 글 쓰기	`W` `W`

글 수정 (권한 있는 경우)	`E` `E`
댓글 영역으로 이동	`C` `C`

이 페이지의 URL 복사	`S` `S`
맨 위로 이동	`T` `T`
티스토리 홈 이동	`H` `H`
단축키 안내	`Shift` + `/` `⇧` + `/`

1. 풀이

2. 전체 코드

3. 수정한 풀이

4. Reference (다른 풀이)

'Algorithm 문제 풀이 > 백준' 카테고리의 다른 글

티스토리툴바

단축키

내 블로그

블로그 게시글

모든 영역

1. 풀이

2. 전체 코드

3. 수정한 풀이

4. Reference (다른 풀이)

'Algorithm 문제 풀이 > 백준' 카테고리의 다른 글

검색 태그

티스토리툴바

단축키

내 블로그

블로그 게시글

모든 영역