[프로그래머스 - Java] 기둥과 보 설치 (2020 KAKAO BLIND RECRUITMENT)

문제

programmers.co.kr/learn/courses/30/lessons/60061

코딩테스트 연습 - 기둥과 보 설치

1. 기둥과 보를 저장하기 

기둥과 보가 같은 (x, y) 좌표에 있을 수 있기에, 둘을 나누어서 2차원 배열에 저장한다.

기둥은 위쪽으로 보는 오른쪽으로 1칸씩 만들어진다.

근데 아래에서 설명할 설치와 삭제 조건에 따라 범위를 넘는 부분을 검사해야 할 때가 있다.

 

 

위 그림은 예제 2번의 모든 작업을 수행후 만들어지는 모습이다.

프로그래머스의 예제와는 다르게 주어진 x, y로 표를 만들면 아래와 같다.

빨간 막대가 기둥이고, 파란 막대가 보이다.

 

 

위 표는 여덟번 째 작업 [2,0,0,0]을 나타낸 것으로, (2, 0) 기둥이 삭제되는 작업이다.

(2, 0) 기둥을 삭제하면 이와 연결되었던, 아래쪽 위쪽 기둥 2개와 옆으로 연결된 보 4개가 삭제 후에도 조건을 만족하는지를 판단해야 한다.

(2, 0) 아래의 기둥을 판별할 경우, 기존 프로그래머스의 표에서는 인덱스 범위를 넘어 y가 -1인 기둥을 판단해야 할 것이다.

 

그렇기에 벽면의 크기 N을 가로 세로로 1씩 추가해 배열을 구성했다.(마치 Padding을 주는 것과 같음)

가로 세로로 1씩 추가가 되었고 이제 배열에서는 (0, 0) 이 시작이 아니라 진한 회색으로 칠해진 부분

즉, (1, 1) ~ (N+1, N+1)까지에서 기둥과 보가 설치되도록 총배열의 길이를 N+3으로 주었다.

• boolean [][] columns // 기둥 배열 
• boolean[][] beams // 보 배열 

2. 설치와 삭제 

설치할 경우와 삭제할 경우를 나누어 함수를 만들어 주었다.

b값이 0일 경우 삭제 / 1일 경우 설치

• void create(int x, int y, int a) // x좌표, y좌표, 0 :기둥 or 1 : 보
• void delete(int x, int y, int a)

기둥과 보는 설치와 삭제의 조건이 있다.

• 기둥은 바닥 위에 있거나 보의 한쪽 끝 부분 위에 있거나, 또는 다른 기둥 위에 있어야 합니다.
• 보는 한쪽 끝 부분이 기둥 위에 있거나, 또는 양쪽 끝 부분이 다른 보와 동시에 연결되어 있어야 합니다.

위의 조건에 따라 기둥을 세울 수 있는지, 보를 세울수 있는지를 판단하기 위해 아래 두 함수를 만들었다.

설치 가능할 경우 true반환, 불가능할 경우 false 반환 

create 함수에서 아래 두 함수를 호출해 판단한다.

• boolean canColumn(int x, int y)
• boolean canBeam(int x, int y)

삭제의 경우, 어떠한 기둥 또는 보가 삭제되었을 때, 나머지 기둥과 보로 조건을 충족할 수 있어야 한다.

이를 위해 먼저 기둥과 보의 상태를 담고 있는 이차원 배열에서 삭제시킬 기둥과 보를 false로 만들어 삭제시켜 준다.

그 후, 삭제된 이차원 배열에서 설치 판단에 사용된 canColumn, canBeam 함수로 남은 기둥과 보가 조건을 충족하는지 검사한다.

delete 함수에서 canDelete 함수를 호출해, 남아있는 모든 기둥과 보에 대한 설치 가능 여부를 판단한다.

• boolean canDelete(int x, int y)

설치와 삭제의 세부 조건 

• 기둥은 바닥 위에 있거나 보의 한쪽 끝 부분 위에 있거나, 또는 다른 기둥 위에 있어야 합니다.
• 보는 한쪽 끝 부분이 기둥 위에 있거나, 또는 양쪽 끝 부분이 다른 보와 동시에 연결되어 있어야 합니다.

위 조건을 canColumn, canBeam 함수에 구현해보자.

 

(x, y)를 기점으로 먼저 기둥이 되는 조건

1. 기둥이 바닥 위에 있을 때

y좌표 값이 1이라면 바닥에 있는 것이다.

 

2. 보의 한쪽 끝 부분 위에 있을 때

기둥과 같은 지점(x, y)에 보가 있거나, 한 칸 앞의 (x-1, y)의 보가 있다면 가능하다.

 

3. 다른 기둥 위에 있을 때

(x, y-1) 칸에 기둥이 있다면 가능하다.

 

public static boolean canColumn(int x, int y) {
	if(y == 1) { // 기둥이 바닥 위에 있을 때
		return true;
	} else if(beams[x][y] == true || beams[x-1][y] == true) { // 보의 한쪽 끝 부분 위에 있을 때 
		return true;
	} else if(columns[x][y-1] == true) { // 다른 기둥 위에 있을 때 
			return true;
	}
        
	return false;
}

 

보가 되는 조건

1. 한쪽 끝 부분이 기둥 위일 때

(x, y-1), (x+1, y-1)에 기둥이 있다면 가능

 

2. 양쪽 끝 부분이 다른 보와 동시에 연결되어있을 때

(x+1, y), (x-1, y)에 둘 다 보가 있다면 가능 

 

public static boolean canBeam(int x, int y) {
	if(columns[x][y-1] == true || columns[x+1][y-1] == true) { // 한쪽 끝 부분이 기둥 위일 때 
		return true;
	} else if(beams[x+1][y] == true && beams[x-1][y] == true) { // 양쪽 끝 부분이 다른 보와 동시에 연결되어있을 때 
		return true;
	}

	return false;
}

전체 코드

전체적으로 코드를 구성하면 아래와 같다.

 

import java.util.*;

class Solution {
 	static int N;
	static boolean[][] columns;
	static boolean[][] beams;
    
    public int[][] solution(int n, int[][] build_frame) {
        N = n;
		int[][] answer;
		columns = new boolean[N+3][N+3];
		beams = new boolean[N+3][N+3];

		for(int i = 0; i < build_frame.length; i++) {
			int[] frame = build_frame[i];
			int x = frame[0]+1; // 범위를 벗어난 경우를 쉽게 처리하기 위해 1씩 인덱스를 높여 저장 
			int y = frame[1]+1;
			int a = frame[2];
			int b = frame[3];

			if(b == 0) { // 삭제할 경우 
				delete(x, y, a);
			} else { // 설치할 경우 
				create(x, y, a);
			}
		}  

		// 정답 출력 
		ArrayList<int[]> list = new ArrayList<>();
		for(int i = 1; i <= N+1; ++i) {
			for(int j = 1; j <= N+1; ++j) {
				if(columns[i][j]) {
					list.add(new int[] {i-1, j-1, 0}); // 1 높인 인덱스 다시 줄여줌 
				}

				if(beams[i][j]) {
					list.add(new int[] {i-1, j-1, 1});
				}
			}
		}

		answer = new int[list.size()][3];
		for(int i = 0; i < answer.length; i++) {
			answer[i][0] = list.get(i)[0];
			answer[i][1] = list.get(i)[1];
			answer[i][2] = list.get(i)[2];
		}

		return answer;
    }
    
	// 설치하기 
	public static void create(int x, int y, int a) {
		if(a == 0) { // 기둥일 때 
			if(canColumn(x, y)) {
				columns[x][y] = true;
			}
		} else { // 보일 때 
			if(canBeam(x, y)) {
				beams[x][y] = true;
			}
		}
	}

	// 삭제하기 
	public static void delete(int x, int y, int a) {
		if(a == 0) { // 기둥일 때, 일단 기둥 삭제 
			columns[x][y] = false;	
		} else { // 보일 때, 일단 보 삭제 
			beams[x][y] = false;
		}

		// 삭제 후 남은 기둥과 보가 요건에 충족하는지 다시 세우면서 확인 
		if(!canDelete(x, y)) { // 삭제할 수 없다면 
			if(a == 0) 
				columns[x][y] = true; // 기둥 원상태로 
			else 
				beams[x][y] = true; // 보 원상태로 
		}    
	}

	public static boolean canDelete(int x, int y) {
		for(int i = 1; i <= N+1; i++) {
			for(int j = 1; j <= N+1; j++) {
				if(columns[i][j] && !canColumn(i, j))  // 기둥 삭제 가능한지 확인 
					return false;

				if(beams[i][j] && !canBeam(i, j))  // 보 삭제 가능한지 확인 
					return false;
			}
		}
		return true;
	}

	// 기둥이 설치 가능한지 판별 
	public static boolean canColumn(int x, int y) {
		if(y == 1) { // 기둥이 바닥 위에 있을 때
			return true;
		} else if(beams[x][y] == true || beams[x-1][y] == true) { //보의 한쪽 끝 위에 있을 때 
			return true;
		} else if(columns[x][y-1] == true) { // 다른 기둥 위에 있을 때 
			return true;
		}

		return false;
	}

	// 보가 설치 가능한지 판별 
	public static boolean canBeam(int x, int y) {
		if(columns[x][y-1] == true || columns[x+1][y-1] == true) { //한쪽 끝 부분이 기둥 위일 때 
			return true;
		} else if(beams[x+1][y] == true && beams[x-1][y] == true) { // 양쪽 끝 부분이 다른 보와 동시에 연결되어있을 때 
			return true;
		}

		return false;
	}
}

GITHUB

GITHUB 코드에는 solution 함수를 포함한 메인 함수와 클래스가 구현되어 있습니다.

 

KwonMinha/Programmers