developer-ellen
인간 디버거의 로그 찍기
developer-ellen
전체 방문자
오늘
어제
  • 분류 전체보기 (217)
    • 회고록 (0)
    • 취뽀 및 커리어 여정의 Stack (2)
      • SSAFY 7기 (2)
    • 프로그래밍공부 (24)
      • c++ (0)
      • JAVA (3)
      • Spring (5)
      • design pattern (3)
      • BackDB (1)
      • Servlet&JSP (3)
      • Vue (4)
      • JPA (4)
      • Infra (1)
      • Linux (0)
    • AI (3)
      • papers (3)
      • trend (0)
    • 프로젝트진행 (0)
      • 데이터베이스 (0)
      • 서버개발 (0)
      • 인공지능 (0)
      • 하루정리 (0)
    • 포트폴리오 (0)
    • 알고리즘 (158)
      • 알고리즘문풀 (155)
      • 알고리즘공부 (3)
    • 통계공부 (15)
      • 시계열분석 (15)
      • 회귀분석 (0)
    • CS (14)
      • 컴퓨터네트워크 (4)
      • 운영체제 (8)
      • 데이터베이스 (2)
    • 주저리주저리 (0)
      • 필사 (0)
    • 취업관련정보 (0)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • 삼성코테파이썬준비
  • 삼성코테기출자바풀이
  • ARIMA모형
  • 통계학
  • 코테파이썬
  • 삼성코테자바꿀팁
  • 백준파이썬풀이
  • 카카오코테
  • Arima
  • 삼성코테준비
  • SW역량테스트파이썬
  • c++디자인패턴
  • BOJ파이썬풀이
  • SW역량테스트파이썬풀이
  • 삼성코테구현문제추천
  • MA모형
  • 카카오코테java풀이
  • 삼성코테자바준비
  • 운영체제인터럽트
  • 삼성코테구현풀이
  • 삼성코테파이썬
  • 시계열분석
  • c++ 빌더 패턴
  • 삼성코테파이썬풀이
  • 시계열
  • 삼성코테자바풀이
  • 통계분석
  • AR모형
  • 삼성코테기출
  • 데이터분석

최근 댓글

최근 글

티스토리

hELLO · Designed By 정상우.
developer-ellen

인간 디버거의 로그 찍기

알고리즘/알고리즘문풀

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

2021. 10. 15. 11:05

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

출처 

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

 

14890번: 경사로

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

www.acmicpc.net

 

** 해결법 참고

(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;
	}
	


}

 

 

'알고리즘 > 알고리즘문풀' 카테고리의 다른 글

BOJ - 감시 15683번 (python)  (0) 2021.10.15
BOJ - 톱니바퀴 14891번 (python, JAVA)  (0) 2021.10.15
BOJ - 스타트와 링크 14889번 (python)  (4) 2021.10.14
BOJ - 연산자 끼워넣기 14888번 (python)  (0) 2021.10.14
BOJ - 로봇 청소기 14503번 (python)  (0) 2021.10.14
    '알고리즘/알고리즘문풀' 카테고리의 다른 글
    • BOJ - 감시 15683번 (python)
    • BOJ - 톱니바퀴 14891번 (python, JAVA)
    • BOJ - 스타트와 링크 14889번 (python)
    • BOJ - 연산자 끼워넣기 14888번 (python)
    developer-ellen
    developer-ellen

    티스토리툴바