[백준] code.plus(시뮬레이션과 구현,JAVA)1917번, 정육면체 전개도

문제 링크

1917번: 정육면체 전개도

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

동적 계획법

모든 연산을 수행하면 똑같은 연산을 중복되게 수행하게 되는데 다이나믹 프로그램은 연산한 내용을 따로 저장하여 효율적으로 작성한 프로그램입니다.

 

더 자세한 내용은 링크를 남겨두겠습니다.

동적 계획법 - 위키백과, 우리 모두의 백과사전

이 문제에 핵심은

1. 6×6에 배열에 있는 종이를 접어서 정육면체를 만들 수 있는지 확인해야 한다.

2. 정육면체를 만들 수 있으면 yes, 만들 수 없으면 no를 결과로 출력합니다.

 

배열에 존재하는 종이를 접을때마다 정육면체를 주사위처럼 돌리면서 정육면체가 되는지 확인하였습니다.

 

만약 입력에 정육면체를 만들 수 있는 종이가 주어진다면 어떻게 시작하든 결국 정육면체가 될 것입니다.

 

정육면체의 각 면을 가리키는 인덱스

1 : 아랫면

2 : 아랫면 기준 남쪽 방향

3 : 윗면

4 : 아랫면 기준 북쪽 방향

5 : 아랫면 기준 서쪽 방향

6 : 아랫면 기준 동쪽 방향

 

 

제가 작성한 과정을 천천히 설명해보도록 하겠습니다.

 

1. 입력되는 종이는 3개이므로 각 종이에 대한 정보를 배열에 저장합니다.

 

2. 입력된 배열에 값에서 처음 만나는 종이를 아랫면으로 기준으로 합니다.

 = startPoint함수

 

3. 아랫면을 기준으로 종이 접기를 시작합니다.

 = cubeMake함수

 

1) 깊이 우선 탐색으로 아랫면을 기준으로 남/동/서/북으로 접기 시작합니다.

남쪽방향으로 접으면 : down함수

동쪽방향으로 접으면 : right함수

서쪽방향으로 접으면 : left함수

북쪽방향으로 접으면 : up함수

 

종이를 접으면 그 방향으로 주사위가 움직이는 것처럼 정육면체를 움직여 이동한 방향이 아랫면이 되도록 합니다.

 

해당 깊이 탐색이 종료되면 원래 상태로 주사위를 돌리는 과정을 취합니다.

 = cubeReverse함수

 

4. 모든 종이를 접고나서 정육면체의 형태가 되어있으면 yes, 아니면 no를 출력하였습니다.

 = cubeCheck함수

 

1) 정육면체의 형태가 되어있다는 것을 확인하기 위해서

 

종이를 접을 때 각 아랫면이 채워졌다고 배열에 저장한 뒤

 

종이를 모두 접은 후 배열에 값들을 확인하여 모든 값이 0이 아니면 정육면체가 되었다고 표현할 수 있습니다.

 

• BufferedReader를 사용하여 입력 값을 받았습니다.
• StringTokenizer를 이용하여 종이의 정보를 저장하였습니다.
• 위에서 설명한 순서대로 적용한 뒤 yes, no를 BufferedWriter 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

 

import java.io.*;
import java.util.*;
public class Main {
	static int[] dice;
	static int[] dy = {1, 0, 0, -1};	//남,동,서,북 y값 변경
	static int[] dx = {0, 1, -1, 0};	//남,동,서,북 x값 변경
	static int row, col;	//첫 아랫면이 되는 row값과 col값
	public static void main(String[] args)throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        	//입력값 처리하는 BufferedReader
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        	//결과값 출력하는 BufferedWriter
		StringTokenizer st;
        	//1.
		for(int i=0;i<3;i++) {
			int[][] arr = new int[6][6];
			boolean[][] visited = new boolean[6][6];
			dice = new int[7];
			for(int j=0;j<6;j++) {
				st = new StringTokenizer(br.readLine()," ");
				for(int s=0;s<6;s++) {
					arr[j][s] = Integer.parseInt(st.nextToken());
				}
			}
			startPoint(arr);	//2.
			cubeMake(arr, visited, row, col);	//3.
			if(cubeCheck())		//4.
				bw.write("yes\n");
			else
				bw.write("no\n");
		}
		bw.flush();		//결과 출력
		bw.close();
		br.close();
	}
    	//종이를 접는 함수
	static void cubeMake(int[][] arr, boolean[][] visited, int row, int col) {
		int[] temp = new int[7];
		dice[1] = 1;		//아랫면 확인
		visited[row][col] = true;	//방문 확인
		for(int i=0;i<4;i++) {
			int tempRow = row + dy[i];
			int tempCol = col + dx[i];
			if(tempRow>=0 && tempCol>=0 && tempRow<6 && tempCol<6 && !visited[tempRow][tempCol]) {
				if(arr[tempRow][tempCol]==1) {
					cubeChange(i, temp);	//정육면체 회전
					cubeMake(arr, visited,tempRow,tempCol);	//종이 접기
					cubeReverse(i, temp);	//정육면체 되돌리기
				}
			}
		}

	}
    	//정육면체 회전 되돌아오기 함수
	static void cubeReverse(int direction, int[] temp) {
		cubeChange(3-direction, temp);
	}
    	//정육면체 회전 함수
	static void cubeChange(int direction, int[] temp) {
		if(direction == 0)		//남쪽
			down(temp);
		else if(direction == 1)	//동쪽
			right(temp);
		else if(direction == 2)	//서쪽
			left(temp);
		else		//북쪽
			up(temp);
		
		tempToDice(temp);	
	}
    	//정육면체 회전된 값 적용 함수
	static void tempToDice(int[] temp) {
		for(int i=1;i<7;i++) 
			dice[i] = temp[i];
	}
    	//종이의 첫 지점을 아랫면으로 설정하는 함수
	static void startPoint(int[][] arr) {
		for(int i=0;i<6;i++) {
			for(int j=0;j<6;j++) {
				if(arr[i][j] == 1) {
					row = i;
					col = j;
					return;
				}
			}
		}
	}
    	//정육면체가 되었는지 확인하는 함수
	static boolean cubeCheck() {
		for(int i=1;i<7;i++) {
			if(dice[i]==0)
				return false;
		}
		return true;
	}
    	//주사위가 아랫면 기준 남쪽방향으로 굴러갈 때 정육면체 변화
	static void down(int[] temp) {
		temp[4] = dice[1];
		temp[1] = dice[2];
		temp[2] = dice[3];
		temp[3] = dice[4];
		temp[5] = dice[5];
		temp[6] = dice[6];
	}
    	//주사위가 아랫면 기준 동쪽방향으로 굴러갈 때 정육면체 변화
	static void right(int[] temp) {
		temp[5] = dice[1];
		temp[2] = dice[2];
		temp[6] = dice[3];
		temp[4] = dice[4];
		temp[3] = dice[5];
		temp[1] = dice[6];
	}
    	//주사위가 아랫면 기준 서쪽방향으로 굴러갈 때 정육면체 변화
	static void left(int[] temp) {
		temp[6] = dice[1];
		temp[2] = dice[2];
		temp[5] = dice[3];
		temp[4] = dice[4];
		temp[1] = dice[5];
		temp[3] = dice[6];
	}
    	//주사위가 아랫면 기준 북쪽방향으로 굴러갈 때 정육면체 변화
	static void up(int[] temp) {
		temp[2] = dice[1];
		temp[3] = dice[2];
		temp[4] = dice[3];
		temp[1] = dice[4];
		temp[5] = dice[5];
		temp[6] = dice[6];
	}
}