| 시간 제한 | 메모리 제한 |
| 1초 | 128MB |
문제
아래에 주어진 전개도의 점선 부분을 접어서 주사위 모양의 정육면체를 만들 수 있는지를 생각해 보자. 전개도의 각 면은 1에서 6까지 서로 다른 정수로 표시되어 있다.
전개도 (1)은 정육면체로 접을 수 있지만, 전개도 (2)는 정육면체로 접을 수 없다. 입력으로 주어진 전개도를 정육면체로 접을 수 있는지를 알아보는 프로그램을 작성하시오.
입력
입력은 여섯 줄로 되어 있으며 각 줄에는 0에서 6까지의 정수들이 여섯 개 있고, 숫자 사이에는 빈칸이 하나씩 있다. 1에서 6까지의 숫자는 전개도의 면을 나타내고, 0은 전개도의 바깥 부분을 나타낸다.
출력
입력된 전개도를 정육면체로 접을 수 있으면, 정육면체에서 1번으로 표시된 면의 맞은 편 면의 번호를 출력하고, 정육면체로 접을 수 없으면 0을 출력한다.
풀이
처음 봤을 때 어떤 방식으로 접근해야 할지 고민이 많았다.
1. 탐색 방향을 중심으로
일단 이건 어떻게 접근하든 같을 거라고 생각했다. 면에 번호를 붙여서 관리해야 한다. 입체를 표현할 수 있는 자료구조를 만들려면 선형 구조로는 택도 없기 때문에 여기에 그래프를 접목했다.
1번 면을 탐색 시작 지점으로 설정해서 주어진 6*6의 board 배열을 탐색한다. board[x][y]에서 처음으로 0이 아닌 숫자를 발견하게 되면 (x, y)를 탐색 시작 위치로 설정하고 cube[1]에 board[x][y]의 값을 저장한다. 여기서부터는 DFS로 board에서 탐색을 시작하고, 탐색을 성공한 방향에 따라 cube 위에서 정보를 저장할 면을 찾으러 이동한다. 여기서 한 가지 어려운 점이 있는데, 탐색 방향에 따라 cube의 면을 이동할 때 DFS에서 탐색 방향과 cube에서 면 이동 방향이 다르다는 것이다.
예를 들어 이런 경우 "1-2-3" 이렇게 나란히 있는 경우, 1번 면에 1을 저장하면 3번 면에 2를 저장하고 6번 면에 3을 저장하게 되는 셈인데 이렇게 나란히 있다면 방향이 일정해서 참 좋지만 오른쪽 같은 경우는 굉장히 복잡해진다. 1번 면에 1을 저장하고 방향 맞춰서 2번 면에 2, 3번 면에 3을 저장하면 4는 6번 면으로 가야하고 5는 4번 면으로 간다. 이런 방향을 조정하는 것이 엄청 까다로워진다. 생각을 확장해서 각 면의 연결 관계를 그래프로 나타내봤다.
회전 방향을 x,y,z로 나누었다. 그리고 각 면의 연결 관계를 노드로 나타냈고, 방향에 따라 색깔로 구분해봤다. 이러면 어떻게 어떤 면에서 현재 방향이 주어졌을 때, 다음 탐색 방향이 결정되면 어떤 노드를 타야할 지 알 수 있고, 그러면 연결된 면을 잘 찾아갈 수 있지 않을까..?
...
어찌 될 것 같긴한데 이걸 정리하다가 다른 아이디어가 떠올라서 일단 이 생각은 여기서 멈췄다.
2. 육면체의 윗면을 중심으로
그림을 좀 다시 그렸다. 다시 면에 번호를 붙였다. 어차피 리스트에 담을거니까 0번부터 5번까지로. 이번에는 육면체를 굴리되, 윗면과 방향이 항상 고정되도록 할거다. 어떤 느낌이냐면, 앞선 방법이 종이의 면을 직접 접어가며 육면체를 만드는 방법이라면 이번 방법은 이미 만들어진 빈 육면체 위에 종이를 올려두고, 육면체를 굴리며 탐색해 면에 있는 숫자를 육면체에 새기는 것이다.
이 방법으로 얻을 수 있는 효과는 방향의 고민을 하지 않아도 된다는 것이다. cube[0]이 항상 위로 오도록 하고, 이걸 기준으로 상,하,좌,우의 면을 탐색해 발견한 방향으로 육면체를 굴려버리면서 값의 위치를 바꿔주는 거다. 그러니까 1번 면에 뭘 했으니까 다음은 2번일지 3번일지 찾는 것이 아니라 매 탐색마다 육면체에 적힌 숫자들의 자리를 바꿔버려 새로운 면을 찾았을 때 윗면(cube[0])이 비어있는 칸이 되도록 만들어버리는 것이다. 이러면 육면체에서 굴리는 방향을 탐색 방향과 완전히 동기화 시킬 수 있다. 이렇게 간단히 정리되는 것을 보니 이쪽이 정해인 것 같다.
3. 구현
탐색을 시작할 위치를 먼저 찾아 DFS를 시도하기로 했다. 왜냐면 육면체를 계속 굴려주는데 BFS로 탐색이 시도되면 모든 탐색마다 육면체의 상태를 관리해줘야 하기 때문에 메모리에서 손해가 발생한다. 어차피 찾아야 할 면은 6개 뿐이니 DFS로 해도 시간은 거의 0이나 다름없다.(그렇게 치면 6개의 BFS 큐도 메모리 거의 안먹는데...)
board[x][y] 위치에서 처음으로 0이 아닌 값을 발견하면 (x,y)를 탐색 시작 지점으로 정하고 cube[0]을 board[x][y]로 정한다. 그리고 상하좌우로 탐색을 시작해 만약 아래쪽에서 다음 값을 찾으면 육면체를 반대 방향인 위쪽으로 굴려준다. 2.의 그림 속 인덱스에 따르면 이런식이다.
tmp = cube[0]
cube[0] = cube[1]
cube[1] = cube[5]
cube[5] = cube[3]
cube[3] = tmp
4방향 모두에 이렇게 굴리기를 적용해주고 탐색한 위치인 (dx,dy)에 대해 visit[dx][dy]를 방문처리, DFS를 시도한다. 그리고 DFS를 탈출할 때는 탐색한 방향으로 육면체를 다시 굴려 원상복구 시켜준다. 탐색을 시도하다가 육면체를 굴렸는데 cube[0]이 0이 아닌 경우는 전개도가 잘못된 것이기 때문에 False를 반환하고 DFS를 탈출한다.
탐색이 끝났을 때 육면체가 잘 완성되었는지 확인하려면 cube배열에 1,2,3,4,5,6이 모두 1개씩 포함되었는지 확인하면 된다. 1이 저장된 면 번호를 찾아 반대 방향 면을 출력해주면 끝.
놀랍게도 이 문제는 1999년 한국 정보올림피아드 초등부 2번 문제다. 이 문제를 1년 전 만났을 때, 출처를 보는 순간 깨달았다. "여기는 괴물 천지구나. 이직은 걍 접자."
정답 코드
# 2642: 전개도
import sys
input = sys.stdin.readline
d = [(-1,0),(0,1),(1,0),(0,-1)]
board = [list(map(int,input().split())) for _ in range(6)]
visit = [[0]*6 for _ in range(6)]
cube = [0]*6
dir = 0
# 육면체 굴리기
def turn(dir):
tmp = cube[0]
if dir == 0:
cube[0] = cube[3]
cube[3] = cube[5]
cube[5] = cube[1]
cube[1] = tmp
elif dir == 1:
cube[0] = cube[2]
cube[2] = cube[5]
cube[5] = cube[4]
cube[4] = tmp
elif dir == 2:
cube[0] = cube[1]
cube[1] = cube[5]
cube[5] = cube[3]
cube[3] = tmp
else:
cube[0] = cube[4]
cube[4] = cube[5]
cube[5] = cube[2]
cube[2] = tmp
# 깊이우선탐색
def dfs(x,y):
for i in range(4):
dx = x+d[i][0]
dy = y+d[i][1]
if 0<=dx<6 and 0<=dy<6 and not visit[dx][dy] and board[dx][dy]:
visit[dx][dy] = 1
turn(i)
# 윗면이 비어있지 않은 경우
if cube[0]: return False
cube[0] = board[dx][dy]
if not dfs(dx,dy): return False
# 육면체 원상복구
turn((i+2)%4)
return True
# 탐색이 잘 끝났는지 확인
def check():
count = 0
# 6개의 면만 주어졌는지 확인
for i in range(36):
if board[i//6][i%6]: count += 1
if count == 6: pass
else: return False
# 육면체의 모든 면이 1~6으로 되었는지 확인
if sorted(cube) == [1,2,3,4,5,6]: pass
else: return False
return True
x,y = 0,0
for i in range(36):
if board[i//6][i%6]:
x = i//6
y = i%6
visit[x][y] = 1
cube[0] = board[x][y]
break
dfs(x,y)
if check():
t = cube.index(1)
if t == 0: print(cube[5])
elif t == 1: print(cube[3])
elif t == 2: print(cube[4])
elif t == 3: print(cube[1])
elif t == 4: print(cube[2])
else: print(cube[0])
else: print(0)
