BOJ - 경사로 14890번 (python, JAVA)

❓ 문제 - 백준 경사로 14890번 - python, JAVA 풀이법

출처 

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

14890번: 경사로

 

** 해결법 참고

(https://pacific-ocean.tistory.com/368)

해당 블로그의 해결법을 참조하여 공부하였습니다...

 

📝 문제해결법

1. 이 문제는 구현으로 풀었다.

• 일차원 리스트(한 줄)로 길을 지나갈 수 있는지 없는지를 check() 함수를 통해 확인한다.
• 특히, 한 행으로 만들어지는 일차원 리스트(line)과 한 열로 만들어지는 일차원 리스트(line)에 대해 다 확인하여 지나갈 수 있는 길을 확인하는 것이 특징이다.

2. check()

• visited 방문 리스트를 활용하여 경사로가 만들어졌을 때 True 처리 해준다.
• line (일차원 리스트)에 대해 칸의 높이가 같다면 칸을 건널 수 있기 때문에 continue
• 만약 옆에 놓인 칸과 현재 칸의 높이 차이가 2이상이면 경사로를 놓을 수 없기 때문에 False 반환
• 현재 칸과 옆의 칸의 높이 차이가 1일 때, 현재 칸이 옆의 칸보다 높이가 크다면 옆칸부터 해당 경사로의 길이까지 칸의 높이가 동일한지 체크하며 경사로가 만들어지는지 확인
• 현재 칸과 옆의 칸의 높이 차이가 1일 때, 현재 칸이 옆의 칸보다 높이가 작다면 현재 칸부터 현재칸 - 경사로의 길이 인 곳을 칸의 높이가 동일한지 체크해서 경사로가 만들어지는지 확인
• 경사로를 만들어지는지 확인할 때 visited 리스트 값이 True, 즉 해당 칸이 이미 경사로가 만들어졌다면 지나갈 수 없어서 False 반환

 

 

💻 소스코드 (python)

n, l = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(n)]
answer = 0
def check(line, l):
    visited = [False for _ in range(n)]
    for i in range(0, n-1):
        if line[i] == line[i+1]:
            continue
        elif abs(line[i]-line[i+1]) > 1:
            return False
        elif line[i] > line[i+1]:
            temp = line[i+1]
            for j in range(i+1, i+l+1):
                if 0 <= j < n:
                    if temp != line[j]:
                        return False
                    elif visited[j]:
                        return False
                    visited[j] = True
                else:
                    return False
        else:
            temp = line[i]
            for j in range(i, i-l, -1):
                if 0 <= j < n:
                    if temp != line[j]:
                        return False
                    elif visited[j]:
                        return False
                    visited[j] = True
                else:
                    return False
    return True


for g in graph:
    if check(g, l):
        answer += 1

for i in range(n):
    temp = []
    for j in range(n):
        temp.append(graph[j][i])
    if check(temp, l):
        answer += 1

print(answer)

 

💻 소스코드 (java)

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

public class Main_14890 {
	public static int n, l;
	public static int[][] map;
	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());
		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;
		for(int i=0;i<n;i++) {
			if(check(map[i])) cnt++;

		}
		
		// 세로
		for(int j=0;j<n;j++) {
			int[] arr = new int[n];
			for(int i=0;i<n;i++) {
				arr[i] = map[i][j];
			}
			
			if(check(arr)) cnt++;
	
		}
		
		System.out.println(cnt);

	}
	
	public static boolean check(int[] arr) {
		boolean[] install = new boolean[n];
		for(int i=0;i<n-1;i++) {
			if(arr[i] == arr[i+1]) continue;
			else if (Math.abs(arr[i] - arr[i+1]) >= 2) return false;
			else if (arr[i] > arr[i+1]) {
				int temp = arr[i+1];
				for(int j=i+1;j<i+l+1;j++) {
					if(0 <= j && j < n) {
						if(temp != arr[j]) return false;
						if(install[j]) return false;
						install[j] = true;
					} else {
						return false;
					}
				}
			} else if (arr[i] < arr[i+1]) {
				int temp = arr[i];
				for(int j=i;j>=i-l+1;j--) {
					if(0 <= j && j < n) {
						if(temp != arr[j]) return false;
						if(install[j]) return false;
						install[j] = true;
					} else {
						return false;
					}
				}
			}
		}
		
		return true;
	}
	


}