[Algorithm] BOJ-14890 Java로 문제풀이 (구현)

---

안녕하세요 Coding-Knowjam입니다.

오늘은 백준 온라인 저지에 있는 문제를 풀어보겠습니다.

문제의 링크는 아래에 있으니 문제를 먼저 읽고 오시길 바랍니다.

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

 

1. 문제 해설

• 난이도 : 골드 3
• 문제 접근 키워드 : 구현

사실 이번 문제는 이렇다 할 알고리즘보다는 문제에서 요구하는 제약조건에 맞게 동작하도록 구현을 하면 되는 문제입니다.

구현 문제는 개발자마다 코드가 다르기 때문에 얘는 이렇게 풀었구나 정도로 참고하시면 될 것 같습니다.

알고리즘이 특별하게 필요한 문제가 아니라서 본인의 스타일에 맞게 구현만 하시면 됩니다.

그럼 코드를 작성해보겠습니다.

 

2. Java 코드로 구현

package study.blog.codingnojam.algorithm;

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

public class BOJ_14890 {
	
	public static void main(String[] args) throws IOException {
		// 입력정보 받기
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] info = br.readLine().split(" ");
		
		// 지도로 사용 할 배열 초기화
		int[][] map = new int[Integer.parseInt(info[0])][Integer.parseInt(info[0])];
		// 지도를 세로로 지나가야하는 길도 계산해야하는데 편하게 계산하기위해 지도를 90도 돌렸습니다. 
		int[][] rotateMap = new int[Integer.parseInt(info[0])][Integer.parseInt(info[0])];
		// 경사로의 길이
		int L = Integer.parseInt(info[1]);
		
		// 지도 배열 초기화
		for (int i = 0; i < map.length; i++) {
			String[] temp = br.readLine().split(" ");
			for (int j = 0; j < map[i].length; j++) {
				map[i][j] = Integer.parseInt(temp[j]);
			}
		}
		
		// 90도 돌린 지도 배열 초기화
		for (int i = 0; i < rotateMap.length; i++) {
			for (int j = 0; j < rotateMap[i].length; j++) {
				rotateMap[i][j] = map[Integer.parseInt(info[0])-1-j][0+i];
			}
		}
		
		// 지나갈 수 있는 길의 개수를 저장 할 변수
		int value = 0;
		// 가로로 지나가는 길 계산 (초기 지도)
		value = value + roadCount(L, map);
		// 가로로 지나가는 길 계산 (90도 돌린 지도)
		value = value + roadCount(L, rotateMap);
		
		// 출력
		System.out.println(value);
	}
	
	//가로로 지나가는 길을 계산하기 위한 메서드
	private static int roadCount(int slopeLength, int[][] map) {
		// 길 개수 저장 변수
		int count = 0;
		for (int i = 0; i < map.length; i++) {
			// 경사로를 설치 했는지 여부 체크를 위한 배열
			boolean[] slopeChk = new boolean[map.length];
			// 현재 행이 지나갈 수 있는 길인지 체크를 위한 변수
			boolean roadChk = false;
			// 현재 칸과 다음 칸을 비교해가면서 진행할 것이기 때문에
			// 전체 반복횟수는 배열의 길이-1 입니다.
			for (int j = 0; j < map[i].length-1; j++) {
				// 현재 칸과 다음 칸의 높이가 동일 할 경우 현재 행은 지나갈 수 있음
				if(map[i][j] == map[i][j+1]) {
					roadChk = true;
				}
				// 현재 칸보다 다음 칸의 높이가 1만큼 큰 경우
				else if(map[i][j] - map[i][j+1] == -1) {
					// 경사로를 설치했을 때 영역을 벗어나지 않아야 함
					if(j - slopeLength+1 >= 0) {
						// for문 내부에서 이동 가능 여부 체크를 위한 임시변수
						boolean tempChk = false;
						// 경사로 설치를 위해 길이만큼 높이 체크
						for(int k=0; k<slopeLength; k++) {
							// 현재 칸에서 경사로 길이만큼 뒤로 이동하면서 경사로를 설치함
							// 이 때 해당 위치에 경사로는 설치되어 있지 않아야 함
							if(map[i][j-k] == map[i][j] && !slopeChk[j-k]) {
								slopeChk[j-k] = true;
							}else {
								// 경사로가 설치되있거나, 높이가 일정하지 않으면 지나갈 수 없음
								tempChk = true;
							}
						}
						// 임시체크변수가 true면 지나갈 수 없는 행이므로 다음 행 이동
						if(tempChk) {
							roadChk = false;
							break;
						}else {
							// false면 경사로 설치 완료
							roadChk = true;
						}
					}else {
						// 경사로를 설치했는데 영역을 벗어나면 현재 행은 못 지나가므로 다음 행으로 이동
						roadChk = false;
						break;
					}
				}
				// 현재 칸이 다음 칸보다 1만큼 더 큰 경우
				else if(map[i][j] - map[i][j+1] == 1) {
					// 경사로를 설치할 때 영역을 벗어나지 않아야 함
					if(j + slopeLength < map.length) {
						// 내부 for문에서 지나감 여부를 체크하기 위한 변수
						boolean tempChk = false;
						// 현재 칸이 더 크기 때문에 경사로를 다음 칸부터 설치해야 함
						// 그러므로 경사로가 설치 된 마지막 위치부터 다시 높이 비교를 시작해야 하므로
						// 경사로가 설치된 마지막 위치의 인덱스 저장을 위한 변수
						int tempIndex =0;
						// 경사로 설치를 위해 길이만큼 높이 체크
						for(int k=1; k<=slopeLength; k++) {
							// 1칸씩 뒤로 이동하면서 높이가 같은지 체크
							if(map[i][j+k] == map[i][j+1]) {
								// 높이가 같으면 경사로 설치
								slopeChk[j+k] = true;
								// 설치한 경사로의 마지막 위치 인덱스 저장
								tempIndex = j+k;
							}else {
								// 높이가 같지 않으면 경사로를 설치할 수 없으므로 못 지나감
								tempChk = true;
							}
						}
						// 임시체크변수가 true면 현재 행은 못 지나가므로 다음 행 이동
						if(tempChk) {
							roadChk = false;
							break;
						}else {
							// false면 경사로 설치 완료
							roadChk = true;
							// 경사로가 설치된 마지막 위치부터 다시 높이 비교를 시작하기 위해
							// 인덱스 변경 (-1을 해준 이유는 for문이 반복될 때 j+1이 되기 때문)
							j = tempIndex-1;
						}
					}else {
						// 경사로를 설치했더니 영역을 벗어나면 현재 행은 못 지나감, 다음 행으로 이동
						roadChk = false;
						break;
					}
				}else {
					// 현재 칸과 다음 칸의 차이가 -1, 0, 1이 아닌 경우 지나갈 수 없으므로 다음 행으로 이동
					roadChk = false;
					break;
				}
			}
			// 현재 행이 지나갈 수 있는 길이라면 카운트변수 1 증가
			if(roadChk) {
				count++;
			}
		}
		return count;
	}
}

 

앞에서도 말씀드렸지만 특별한 알고리즘이 필요한 게 아니라 조건 그대로 구현을 하면 됩니다.

아 그리고 문제에서 가로로 지나가는 경우와 세로로 지나가는 경우 모두 체크하도록 요구하고 있습니다.

배열을 90도 돌리면 세로로 지나가는 길이 결국 가로로 지나가는 길을 계산하는 것과 같기 때문에 저는 세로로 계산하는 for문을 하나 더 짜는 것보다는 그냥 배열을 돌려서 계산하도록 구현하였습니다.

제가 구현 문제를 풀 때는 항상 코드가 좀 더러워지는 것 같습니다... ㅠㅠ

그래도 모든 코드마다 주석을 달아놓았으니 조금 지저분해도 천천히 읽어보시면 이해하시는데 무리가 없을 겁니다.

저보다 더 깔끔하게 코드를 작성한 분들도 많으니 문제를 푸시고 나서 공개된 정답 코드를 읽어보시기를 추천드립니다.

감사합니다.

---