[Java] 백준 1917번 : 정육면체 전개도*

1. 문제

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

1917번: 정육면체 전개도

 

 

 

2. 풀이 과정

주사위의 위치와 번호를 이용하는 아이디어는 다른 코드를 보다가 얻어서 아쉽지만,

코드는 보지 않았기에 같은 아이디어라도 다르게 구현할 수 있었던 것 같다.

 

아이디어를 한 줄로 정리해보면, 원래의 주사위를 전개도로 펼친다고 볼 수 있다.

1. 주사위 위치에 따라 1~6번호를 저장하는 배열을 만든다.

2. 위로, 왼쪽으로, 오른쪽으로, 아래로 굴려가면서 배열 정보를 업데이트 해준다.

   2-1. 앞으로, 뒤로 굴리는 건 없으므로 4방향 탐색으로 본다.

   2-2. 이미 사용한 숫자가 나오면, 도면에서 겹치는 부분이 있다는 의미이므로 종료

   2-3. dfs를 사용해서 방문했다가 돌아올 때는 반대로 굴리기 (단, 사용한 숫자와 visited는 복구X)

import java.io.*;

//앞 = 1, 뒤 = 6 | 왼 = 2, 위 = 3, 오 = 4, 밑 = 5
public class Boj1917 {
	static int map[][], dice[];
	static boolean visited[], result;//1~6번
	
	//위0, 오1, 밑2, 왼3, 앞4, 뒤5
	public static void dfs(int x, int y) {
		//위에서부터 시계방향 탐색
		int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
		for(int i=0; i<4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if(nx<0 || nx>=6 || ny<0 || ny>=6 || map[nx][ny]!='1') {continue;}
			if(visited[dice[i]]) {
				result = false;
				return;
			}
			map[nx][ny] = '0';
			visited[dice[i]] = true;
			turn(i);
			dfs(nx, ny);
			turn((i+2)%4);
		}
	}
	
	public static void turn(int n) {
		switch(n) {
		case 0://위로
			dice = new int[] {dice[5], dice[1], dice[4], dice[3], dice[0], dice[2]};
			break;
		case 1://오
			dice = new int[] {dice[0], dice[5], dice[2], dice[4], dice[1], dice[3]};
			break;
		case 2://아래로
			dice = new int[] {dice[4], dice[1], dice[5], dice[3], dice[2], dice[0]};
			break;
		case 3://왼
			dice = new int[] {dice[0], dice[4], dice[2], dice[5], dice[3], dice[1]};
			break;
		}
	}

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuffer sb = new StringBuffer();
		for(int T=1; T<=3; T++) {
			result = true;
			dice = new int[]{2, 3, 4, 5, 1, 6};//위0, 오1, 밑2, 왼3, 앞4, 뒤5

			//0. input
			map = new int[6][6];
			for(int i=0; i<6; i++) {
				String s = br.readLine();
				for(int j=0; j<12; j+=2) {
					map[i][j/2] = s.charAt(j);
				}
			}
			//1. dfs
			outloop:for(int i=0; i<6; i++) {
				for(int j=0; j<6; j++) {
					if(map[i][j]=='1') {
						map[i][j] = '0';
						visited = new boolean[7];
						visited[1] = true;
						dfs(i, j);
						break outloop;
					}
				}
			}
			//2. 출력
			sb.append(result==true?"yes\n":"no\n");
		}
		System.out.println(sb.toString());
	}

}