[ 백준 2642번 ] 전개도

1. 문제

2642번: 전개도

 

2. 풀이

문제에서 요구하는 것은 간단하다. 전개도가 주어졌을 때, 정육면체를 만들 수 있는 전개도인지 판단하고 가능하다면 숫자 1이 써져 있는 면의 반대 면에 위치한 숫자를 출력하는 것이다.

 

그렇다면 당연하게도 우리는 주어진 전개도가 정육면체를 만들 수 있는지 여부를 어떻게 판단할 것인가를 고민해야 한다.

 

2.1 정육면체 전개도의 종류

먼저 정육면체를 만들 수 있는 전개도의 종류는 아래 이미지와 같이 총 11가지가 있다. 그럼 첫 번째로, 11가지 유형에 대해 미리 정의하고 이를 회전시키면서 일치하는 유형이 있는가를 판단하는 방법을 떠올릴 수 있다. 하지만 그렇게 하기는 싫다. brute-force로 해결해도 충분히 가능한 문제이지만 복잡하게 시뮬레이션을 돌리고 싶지는 않기 때문이다. 분명 전개도가 규칙이 존재할 것이란 가정하에 찾아낸 풀이법은 아래와 같다.

이미지 출처: https://sigan.kr/bbs/board.php?bo_table=cm_free&wr_id=1598

 

2.2 전개도와 트리(Tree)

전개도

 

어떤 수학적인 규칙이 존재할까 탐색하던 도중 위 포스팅을 발견하였다. 포스팅에서 얘기하는 짝트리라는 개념에 착안해서 문제를 해결하는 방법을 찾아낼 수 있었다. 정육면체라는 것은 서로 마주하고 있는 면이 총 3쌍으로 구성되어 있다. 또한 마주하고 있는 면 사이에는 반드시 면이 하나 끼여있으므로, 두 면 간의 이동 거리는 2라는 것을 알 수 있다(면이 하나 끼여 있지만, 시작 면에서 두 칸을 이동해야 하므로 2로 정의했다).

 

즉, 이동 거리가 2인 두 면의 쌍을 총 세 쌍을 만들 수 있다면 정육면체 전개도라고 판단할 수 있다. 하지만 여기에 추가적으로 어떻게 전개도 상에서 이동거리가 2인 것을 판단할 수 있을 것인가 라는 문제가 남아 있다. 이것은 전개도 상에서의 규칙으로써 해결할 수 있다.

 

결론부터 얘기하자면, 시작 지점에서 인접한 면의 방향으로 2번 움직여서 면을 만날 수 있다면 두 면은 마주하고 있는 하나의 쌍으로 묶을 수 있다. 먼저 왼쪽 그림을 보자. 1번 면은 2번 면을 남쪽으로 인접하고 있는데, 1번에서 남쪽으로 두 번 이동한다면 6번 면을 만날 수 있고 두 면은 서로 마주보고 있는 면이라는 것을 알 수 있다.

 

그렇다면 오른쪽 그림은 어떨까? 인접해 있는 그 어떤 방향으로도 두 번 연속 이동할 수가 없다. 이것이 핵심이다. 바로, 중간에 어떤 경로가 끼어 있는 것은 상관 없으며 같은 방향으로 두 번 이동할 수 만 있다면 해당 면은 마주보고 있는 한 쌍이라는 것을 알 수 있다. 똑같이 1번 면에서 출발해서 마주보고 있는 면을 탐색해보자.

 

1번 면에 인접한 면은 총 두 개로 먼저 동쪽에 인접한 6번 면을 따라가볼 수 있으나 6번 면은 더 이상 인접한 면이 없으므로 탐색을 중단한다. 다음 남쪽으로 인접한 5번 면을 따라서 탐색을 해보면 과정은 아래와 같다.

• 1 > 남쪽으로 이동 > 5 > 서쪽으로 이동 > 4 > 남쪽으로 이동 > 3

 

처음 1번 면에서 인접한 방향인 남쪽으로 이동 후에, 서쪽으로 이동하긴 했으나 남쪽으로 한 번 더 이동하면 3번 면을 마주할 수 있다. 그리고 1번과 3번은 정육면체에서 마주한 면이라는 것을 알 수 있다.

 

정리하면, 시작 면에서 인접한 면의 방향과 같은 방향으로 두 번 이동할 수 있다면 해당 면은 마주하고 있는 한 쌍이 된다.

그럼 위 이미지와 같은 한 가지 반례를 찾을 수 있게 되는데, 여기서 중요한 한 가지 조건이 추가 된다. 이동거리가 2인 면을 단 하나만 탐색할 수 있어야 한다는 조건을 추가 해줘야만 한다. 3번 면의 경우 서쪽으로 두 칸 이동하면 1번 면을, 동쪽으로 두 칸 이동하면 5번을 만날 수 있으므로, 이는 전개도가 아니라고 판단할 수 있다.

 

2.3 DFS를 통한 해결

위 일련의 과정들을 통해 우리는 어떻게 전개도가 정육면체의 전개도인지를 판단할 수 있는지 알아보았다. 해당 조건들을 각 면(노드)에서 DFS를 통해 적절히 구현해준다면 최종적으로 문제를 풀 수 있다.

 

3. 소스코드

public class dfs_02642_planarFigure {
    static final int[] dy = {-1, 0, 1, 0};
    static final int[] dx = {0, 1, 0, -1};

    static boolean ans = true;

    static int[] pos, face; // 번호가 적힌 각 면의 위치와, 마주하고 있는 면을 기록하기 위한 배열
    static int[][] map; 
    static boolean[][] visit; // 특정 면에서 다른 면으로 방문을 시도했는가 여부를 판단하는 배열

    static void dfs(int y, int x, int originNode, int originDir, int cnt) {
        if (cnt >= 2) return;

        for (int dir = 0; dir < 4; dir++) {
            int ny = y + dy[dir];
            int nx = x + dx[dir];

            if (isOutOfRange(ny, nx) || visit[originNode][map[ny][nx]]) continue;

            int nextNode = map[ny][nx];

            visit[originNode][nextNode] = true;

            // 거리가 2인 경우
            if (cnt == 1 && dir == originDir) {
                // 2번 이동을 통해서 만난 면이 이미 마주보고 있는 면으로 설정되었는지 여부를 판단
                if (face[nextNode] == 0 || face[nextNode] == originNode) {
                    face[originNode] = nextNode;
                    face[nextNode] = originNode;
                } else {
                    ans = false;
                }
                return;
            } else {
                dfs(ny, nx, originNode, originDir, cnt);
            }
        }
    }

    static boolean isOutOfRange(int y, int x) {
        return y < 0 || x < 0 || 6 <= y || 6 <= x || map[y][x] == 0;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        initializeArrays();

        StringTokenizer st;
        for (int i = 0; i < 6; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < 6; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                if (map[i][j] > 0) {
                    pos[map[i][j]] = i * 6 + j;
                    visit[map[i][j]][map[i][j]] = true;
                }
            }
        }

        for (int i = 1; i <= 6; i++) {
            // 인접한 면의 방향으로만 탐색해야 반례 통과 가능
            for (int dir = 0; dir < 4; dir++) {
                int ny = pos[i] / 6 + dy[dir];
                int nx = pos[i] % 6 + dx[dir];

                if (isOutOfRange(ny, nx)) continue;

                dfs(ny, nx, i, dir, 1);
            }
        }

        for (int i = 1; i <= 6; i++) {
            if (face[i] == 0) {
                ans = false;
                break;
            }
        }

        bw.write(ans ? face[1] + "" : "0");
        bw.flush();
        bw.close();
        br.close();
    }

    static void initializeArrays() {
        pos = new int[7];
        face = new int[7];
        map = new int[6][6];
        visit = new boolean[7][7];
    }
}

 

GitHub - kwanik-kor/BOJ: Baekjoon Online Judge - explanation of solved problems and complete code