[백준/파이썬] 29733번: 3차원 지뢰찾기

문제

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

풀이

• 지뢰 큐브의 넓이: $R \times C \times H$
• 모든 칸은 최대 $26$개 인접
• 빈 칸에 인접한 칸의 지뢰의 개수 출력

처음에 문제를 접했을 때 일반적인 3차원 지뢰찾기를 생각하여 6방향으로 찾았었습니다..
'왜 안 돼?' 하고 있다가 나중에서야 26방향인 것을 깨달았습니다..

왜 26방향이냐?

원래 3차원 지뢰찾기의 6방향이라고 하면은

위 그림과 같이 앞,뒤,위,아래에다가 z축 기준 위,아래가 포함이 됩니다.

그러나 26방향은 $(-1,0,1)^3 -1$의 방향을 찾는 것입니다.
선 뿐만 아니라 점이 인접하고 있어도 인접한다고 하기 때문이죠

그래서 위 그림과 같이 $3 \times 3 \times 3$ 크기의 지뢰 큐브는 모든 칸이 인접해있는 것과 같습니다.

왜 (-1,0,1)의 3제곱 -1인가?

x축 기준 (-1,0,1), y축 기준 (-1,0,1), z축 기준(-1,0,1)의 모든 조합을 생각하면 $3^3$ 즉, 27가지가 존재합니다.
그러나 자기 자신의 위치(0,0,0)는 포함시키지 말아야 하기 때문에 -1을 해준 것입니다.

---

이 26가지 방향을 모두 손으로 작성하면 헷갈리기도 하고 잘못 기입될 가능성이 있기 때문에 함수로 구현해보겠습니다.

def direction():
    d = [] # 조합을 저장할 배열
    for dx in (-1,0,1): # x축 3방향
        for dy in (-1,0,1): # y축 3방향
            for dz in (-1,0,1): # z축 3방향
                if dx == 0 and dy == 0 and dz == 0:
                    continue # 자기 자신 제외
                d.append((dx,dy,dz)) 
    return d

이제 구한 이 방향들을 가지고 탐색을 시작하면 됩니다.

def func(board):
    res = [[[0] * c for _ in range(r)] for _ in range(h)] # 0으로 채운 같은 크기의 배열
    
    for z in range(h):
        for y in range(r):
            for x in range(c):
                if board[z][y][x] == '*': # board[z][y][x]가 지뢰일 경우
                    res[z][y][x] = '*' # 결과 배열에 지뢰 추가
                else: # 지뢰가 아닐 경우
                    cnt = 0
                    for dz,dy,dx in directions: # 26방향 탐색
                        nz = z + dz
                        ny = y + dy
                        nx = x + dx
                        if 0 <= nz < h and 0 <= ny < r and 0 <= nx < c: # 범위 내일 경우
                            if board[nz][ny][nx] == '*': # 26방향 중 지뢰가 존재할 경우
                                cnt += 1 # 카운팅
                    res[z][y][x] = cnt % 10 # 반복문 종료 후 값 추가

    return res

방향 탐색만 잘 정의해주면 금방 해결할 수 있는 단순 구현 문제입니다.

코드

import sys
input = sys.stdin.readline

def func(board):
    res = [[[0] * c for _ in range(r)] for _ in range(h)]
    
    for z in range(h):
        for y in range(r):
            for x in range(c):
                if board[z][y][x] == '*':
                    res[z][y][x] = '*'
                else:
                    cnt = 0
                    for dz,dy,dx in directions:
                        nz = z + dz
                        ny = y + dy
                        nx = x + dx
                        if 0 <= nz < h and 0 <= ny < r and 0 <= nx < c:
                            if board[nz][ny][nx] == '*':
                                cnt += 1
                    res[z][y][x] = cnt % 10

    return res

def direction():
    d = []
    for dx in (-1,0,1):
        for dy in (-1,0,1):
            for dz in (-1,0,1):
                if dx == 0 and dy == 0 and dz == 0:
                    continue # 자기 자신 제외
                d.append((dx,dy,dz))
    return d

if __name__ == "__main__":
    r,c,h = map(int,input().split())
    board = [[list(input().rstrip()) for _ in range(r)] for _ in range(h)]
    directions = direction()
    
    answer = func(board)
    for i in range(h):
        for j in range(r):
            print(*answer[i][j], sep='')