[Programmers] 기둥과 보 설치 (JAVA)

2022. 3. 5. 02:38· Algorithm
반응형

- 알고리즘 분류 : 구현

- 사용 언어 : JAVA

- 문제 요점

  1. 기둥과 보를 나눠서 관리.
  2. 건축물을 해제할 때는 해당 건축물을 제거 한 후, 남아있는 건축물의 정합성 테스트를 진행하는 방식
  3. 결과를 반환할 때 문제에 주어진 규칙에 맞게 반환해야함.

소스 설명은 주석을 참고해주세요.

import java.io.IOException;

public class Main {
	
	// 기둥과 보를 따로 관리.
	// 기둥
    public static boolean[][] pillars;
    
    // 보
    public static boolean[][] beams;
    
    // 건설한 구조물의 수
    public static int count = 0;
    
    // 맵의 길이
    public static int length;
    
    // 해당 위치의 보 정합성 체크
    public static boolean checkBeam(int x, int y) {
    	if(y-1 >= 0 && y-1 < length) {
			// 한쪽 끝 부분이 기둥 위에 있을 경우 가능
			if(pillars[x][y-1] == true) {
				return true;
			}
			// 한쪽 끝 부분이 기둥 위에 있을 경우 가능
			if(x+1 >= 0 && x+1 < length) {
				if(pillars[x+1][y-1] == true) {
					return true;
				}
			}
			
			// 양쪽 끝 부분이 다른 보와 동시에 연결되어 있는 경우 가능
			if(x-1 >= 0 && x-1 < length && x+1 >= 0 && x+1 < length) {
				if(beams[x-1][y] == true && beams[x+1][y] == true) {
					return true;
				}
			}
		}
    	
    	// 위의 경우가 아니면 정합성 결과 FALSE
    	return false;
    }
    
    // 해당 기둥 정합성 체크
    public static boolean checkPillar(int x, int y) {
    	// 바닥에 설치 시
		if(y==0) {
			return true;
		}
		
		// 보의 한쪽 끝 부분 위에 설치할 경우 가능
		if(beams[x][y] == true) {
			return true;
		}
		
		// 보의 한쪽 끝 부분 위에 설치할 경우 가능
		if(x-1 >= 0 && x-1 < length) {
			if(beams[x-1][y] == true) {
				return true;
			}
		}
		
		// 기둥 위에 설치할 경우 가능
		if(y-1 >= 0 && y-1 < length) {
			if(pillars[x][y-1] == true) {
				return true;
			}
		}
		
		// 위의 경우가 아니면 정합성 결과 FALSE
		return false;
    }
    
    // 기둥 작업(설치 or 삭제)
    public static void workPillar(int x, int y, int a, int b) {
    	// 설치
    	if(b==1) {
    		// 해당 자리에 설치할 수 있으면 설치
    		if(checkPillar(x,y) == true) {
    			pillars[x][y] = true;
    			count++;
    		}
    	}
    	// 삭제
    	else {
    		// 우선 해당 위치의 구조물을 삭제 및 건축물 갯수 -1 처리 후
    		pillars[x][y] = false;
    		count--;
    		
    		// 남은 건축물들 정합성 테스트 해서 정합성 실패일 경우 원복.
    		for(int i=0; i<length; i++) {
    			for(int j=0; j<length; j++) {
    				
    				// 해당 위치에 기둥이 있을 때
    				if(pillars[i][j] == true) {
    					// 해당 기둥이 조건을 만족하는 지 체크. 조건 만족 안하는 경우 
    					if(checkPillar(i,j) == false) {
    						// 원복
    						pillars[x][y] = true;
    			    		count++;
    			    		return;
    					}
    				}
    				
    				// 해당 위치에 보가 있을 때
    				if(beams[i][j] == true) {
    					// 해당 보가 조건을 만족하는 지 체크. 조건 만족 안하는 경우 
    					if(checkBeam(i,j) == false) {
    						// 원복
    						pillars[x][y] = true;
    			    		count++;
    			    		return;
    					}
    				}
    			}
    		}
    	}
    }

    // 보 작업(설치 or 삭제)
    public static void workBeam(int x, int y, int a, int b) {
    	// 설치 
    	if(b == 1) {
    		// 해당 자리에 설치할 수 있으면 설치
    		if(checkBeam(x,y) == true) {
    			beams[x][y] = true;
    			count++;
    		}
    	}
    	// 삭제
    	else {
    		// 우선 해당 위치의 구조물을 삭제 및 건축물 갯수 -1 처리 후
    		beams[x][y] = false;
    		count--;
    		
    		// 남은 건축물들 정합성 테스트 해서 정합성 실패일 경우 원복.
    		for(int i=0; i<length; i++) {
    			for(int j=0; j<length; j++) {
    				
    				// 해당 위치에 기둥이 있을 때
    				if(pillars[i][j] == true) {
    					// 해당 기둥이 조건을 만족하는 지 체크. 조건 만족 안하는 경우 
    					if(checkPillar(i,j) == false) {
    						// 원복
    						beams[x][y] = true;
    			    		count++;
    			    		return;
    					}
    				}
    				
    				// 해당 위치에 보가 있을 때
    				if(beams[i][j] == true) {
    					// 해당 보가 조건을 만족하는 지 체크. 조건 만족 안하는 경우 
    					if(checkBeam(i,j) == false) {
    						// 원복
    						beams[x][y] = true;
    			    		count++;
    			    		return;
    					}
    				}
    			}
    		}
    	}
    }
    
    public static int[][] solution(int n, int[][] build_frame) {
        // build_frame :  [x, y, a, b]
        // x : 가로 좌표, y : 세로 좌표
        // a - 0 : 기둥, 1 : 보
        // b - 0 : 삭제, 1 : 설치
        
    	length = n+1;
    	
    	pillars = new boolean[length][length];
    	beams = new boolean[length][length];
    	
    	
        for(int i=0; i<build_frame.length; i++){
            int[] curPos = build_frame[i];
            
            // 가로 좌표
            int x = curPos[0];
            
            // 세로 좌표
            int y = curPos[1];
            
            // 0 : 기둥, 1 : 보
            int a = curPos[2];
            
            // 0 : 삭제, 1 : 설치
            int b = curPos[3];
            
            // 교차점 좌표를 기준으로, 보는 오른쪽 / 기둥은 위쪽 방향으로 설치 or 삭제
            
            if(a==0) {
            	workPillar(x, y, a, b);
            }
            else {
            	workBeam(x, y, a, b);
            }
        }
        
        // 건축물의 수만큼 크기 할당.
        // answer[] : [x,y,a] 형식
        int[][] answer = new int[count][3];
        
        int index = 0;
        
        // 데이터 정렬 조건 : x오름차순, y오름차순.
        // 한 좌표에 기둥과 보 둘 다 있을 경우 기둥이 먼저 나오도록 정렬
        for(int i=0; i<length; i++) {
        	for(int j=0; j<length; j++) {
        		if(pillars[i][j] == true) {
        			answer[index] = new int[] {i,j,0};
        			index++;
        		}
        		if(beams[i][j] == true) {
        			answer[index] = new int[] {i,j,1};
        			index++;
        		}
        	}
        }
        
        // answer : [x,y,a] 형식
        return answer; 
    }
	
	public static void main(String[] args) throws IOException {
		int n = 5;
		//int[][] arr = {{1,0,0,1},{1,1,1,1},{2,1,0,1},{2,2,1,1},{5,0,0,1},{5,1,0,1},{4,2,1,1},{3,2,1,1}};
		int[][] arr = {{0,0,0,1},{2,0,0,1},{4,0,0,1},{0,1,1,1},{1,1,1,1},{2,1,1,1},{3,1,1,1},{2,0,0,0},{1,1,1,0},{2,2,0,1}};
		
		solution(n,arr);
	}
}
반응형

'Algorithm' 카테고리의 다른 글

[BAEKJOON] 11404번 : 플로이드 (JAVA)  (0) 2022.03.08
[BAEKJOON] 14889번 : 스타트와 링크 (JAVA)  (0) 2022.03.07
[BAEKJOON] 2294번 : 동전 2 (JAVA)  (0) 2022.03.02
[BAEKJOON] 3190번 : 뱀 (JAVA)  (0) 2022.02.28
[BAEKJOON] 12865번 : 평범한 배낭 (JAVA)  (0) 2022.02.26
'Algorithm' 카테고리의 다른 글
  • [BAEKJOON] 11404번 : 플로이드 (JAVA)
  • [BAEKJOON] 14889번 : 스타트와 링크 (JAVA)
  • [BAEKJOON] 2294번 : 동전 2 (JAVA)
  • [BAEKJOON] 3190번 : 뱀 (JAVA)
멍목
멍목
개발 관련 새롭게 알게 된 지식이나 좋은 정보들을 메모하는 공간입니다.
반응형
멍목
김멍목의 개발블로그
멍목
전체
오늘
어제
  • 분류 전체보기 (514)
    • BE (190)
      • Spring (21)
      • Java (141)
      • Kotlin (6)
      • JPA (22)
    • FE (33)
      • Javascript (16)
      • Typescript (0)
      • React (5)
      • Vue.js (9)
      • JSP & JSTL (3)
    • DB (32)
      • Oracle (22)
      • MongoDB (10)
    • Algorithm (195)
    • Linux (8)
    • Git (6)
    • etc (42)
    • ---------------------------.. (0)
    • 회계 (4)
      • 전산회계 2급 (4)
    • 잡동사니 (2)

블로그 메뉴

  • 홈
  • 관리

공지사항

인기 글

태그

  • 코테공부
  • MongoDB 기초부터 실무까지
  • 자기공부
  • 이펙티브 자바
  • JPA 공부
  • MongoDB with Node.js
  • vue3 공부
  • 더 자바 애플리케이션을 테스트하는 다양한 방법
  • 이펙티브자바
  • MongoDB 공부
  • 자기 공부
  • java 8
  • 자바공부
  • 자기개발
  • 전산회계 2급 준비
  • 자기 개발
  • Oracle
  • Effective Java
  • 알고리즘공부
  • 자바 공부
  • Java to Kotlin
  • 코틀린
  • 자바 개발자를 위한 코틀린 입문
  • 자바 테스팅 프레임워크
  • 코테 공부
  • 프로젝트로 배우는 Vue.js 3
  • junit5
  • 더 자바 Java 8
  • JPA
  • 알고리즘 공부

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.2.0
멍목
[Programmers] 기둥과 보 설치 (JAVA)
상단으로

티스토리툴바

개인정보

  • 티스토리 홈
  • 포럼
  • 로그인

단축키

내 블로그

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

블로그 게시글

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

모든 영역

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

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.