[ BOJ ] 5547 : 일루미네이션 ( GOLD 4 ) / Python

문제

부유한 집안의 상속자 상근이네 집은 그림과 같이 1미터의 정육각형이 붙어있는 상태이다. 크리스마스가 다가오기 때문에, 여자친구에게 잘 보이기 위해 상근이는 건물의 벽면을 조명으로 장식하려고 한다. 외부에 보이지 않는 부분에 조명을 장식하는 것은 낭비라고 생각했기 때문에, 밖에서 보이는 부분만 장식하려고 한다.

위의 그림은 상공에서 본 상근이네 집의 건물 배치이다. 정육각형 안의 숫자는 좌표를 나타낸다. 여기서 회색 정육각형은 건물의 위치이고, 흰색은 건물이 없는 곳이다. 위에서 붉은 색 선으로 표시된 부분이 밖에서 보이는 벽이고, 이 벽에 조명을 장식할 것이다. 벽의 총 길이는 64미터이다.

상근이네 집의 건물 위치 지도가 주어졌을 때, 조명을 장식할 벽면의 길이의 합을 구하는 프로그램을 작성하시오. 지도의 바깥은 자유롭게 왕래 할 수 있는 곳이고, 인접한 건물 사이는 통과할 수 없다.

입력

첫째 줄에 두 개의 정수 W와 H가 주어진다. (1 ≤ W, H ≤ 100) 다음 H줄에는 상근이네 집의 건물 배치가 주어진다. i+1줄에는 W개의 정수가 공백으로 구분되어 있다. j번째 (1 ≤ j ≤ w) 정수의 좌표는 (j, i)이며, 건물이 있을 때는 1이고, 없을 때는 0이다. 주어지는 입력에는 건물이 적어도 하나 있다.

지도는 다음과 같은 규칙에 의해 만들어졌다.

• 지도의 가장 왼쪽 위에 있는 정육각형의 좌표는 (1,1)이다.
• (x,y)의 오른족에 있는 정육각형의 좌표는 (x+1,y)이다.
• y가 홀수 일 때, 아래쪽에 있는 정육각형의 좌표는 (x,y+1)이다.
• y가 짝수 일 때, 오른쪽 아래에 있는 정육각형의 좌표는 (x,y+1)이다.

출력

조명을 장식하는 벽면의 길이의 합을 출력한다.

풀이 과정

건물의 벽면을 장식하기 위해, 정육각형 건물의 주변 둘레를 구해야 한다. 유의해야 할 점은, 건물이 둘러싸고 있는 빈 공간에서는 둘레를 포함하지 않는다는 점이다.

먼저 정육각형 건물의 둘레를 구하고, 외부와 이어지지 않은 빈 공간의 둘레를 제거하여 조명 장식 벽면의 길이 합을 구한다.

 

정육각형 배치를 자세히 살펴보면, 다음과 같은 규칙을 얻을 수 있다.

y가 짝수 일 때 (5, 2) 정육각형의 주변 정육각형 좌표는 다음과 같다.

왼쪽 위 정육각형 : (x - 1, y - 1)

왼쪽 정육각형 : (x - 1, y)

왼쪽 아래 정육각형 : (x - 1, y + 1)

오른쪽 위 정육각형 : (x, y - 1)

오른쪽 정육각형 : (x + 1, y)

오른쪽 아래 정육각형 : (x, y + 1)

 

y가 홀수 일 때 (2, 3) 정육각형의 주변 정육각형 좌표는 다음과 같다.

왼쪽 위 정육각형 : (x, y - 1)

왼쪽 정육각형 : (x - 1, y)

왼쪽 아래 정육각형 : (x, y + 1)

오른쪽 위 정육각형 : (x + 1, y - 1)

오른쪽 정육각형 : (x + 1, y)

오른쪽 아래 정육각형 : (x + 1, y + 1)

 

다음과 같은 주변 정육각형 규칙을 얻어낸 뒤, 먼저 건물 정육각형 둘레를 구한다. 

정육각형 변이 외부와 맞닿아 있거나, 빈 공간과 맞닿아 있다면 1씩 더하며 둘레를 구한다.

row_odd = [-1, -1, -1, 0, 1, 0]
col_odd = [-1, 0, 1, -1, 0, 1]
row_even = [0, -1, 0, 1, 1, 1]
col_even = [-1, 0, 1, -1, 0, 1]
result = 0
for i in range(h):
    for j in range(w):
        if maps[i][j] == 0: 
            continue
        for d in range(6):
            if i % 2 == 0:
                if not (0 <= i + col_even[d] < h and 0 <= j + row_even[d] < w and maps[i + col_even[d]][j + row_even[d]] == 1): 
                    result += 1
            else:
                if not (0 <= i + col_odd[d] < h and 0 <= j + row_odd[d] < w and maps[i + col_odd[d]][j + row_odd[d]] == 1): 
                    result += 1

 

 

정육각형 건물의 둘레를 구했다면, 외부와 연결되지 않은 빈 공간의 둘레를 포함하지 않아야 한다.

가장자리 변에서 BFS 를 수행함으로써, 외부와 연결된 빈 공간을 1로 채워 건물 정육각형 안에 외부와 단절되어 있는 빈 공간을 구한다.

# 외부에서 연결된 0 들을 전부 없애기
def BFS(y, x):
    global maps
    queue = deque()
    queue.append([y, x])
    maps[y][x] = 1

    while queue:
        now = queue.popleft()
        for d in range(6):
            if now[0] % 2 == 0:
                if 0 <= now[0] + col_even[d] < h and 0 <= now[1] + row_even[d] < w and maps[now[0] + col_even[d]][now[1] + row_even[d]] == 0:
                    maps[now[0] + col_even[d]][now[1] + row_even[d]] = 1
                    queue.append([now[0] + col_even[d], now[1] + row_even[d]])
            else:
                if 0 <= now[0] + col_odd[d] < h and 0 <= now[1] + row_odd[d] < w and maps[now[0] + col_odd[d]][now[1] + row_odd[d]] == 0:
                    maps[now[0] + col_odd[d]][now[1] + row_odd[d]] = 1
                    queue.append([now[0] + col_odd[d], now[1] + row_odd[d]])
# Left
for i in range(h):
    if maps[i][0] == 0: BFS(i, 0)
# Right
for i in range(h):
    if maps[i][w-1] == 0: BFS(i, w-1)
# Up
for j in range(w):
    if maps[0][j] == 0: BFS(0, j)
# Down
for j in range(w):
    if maps[h-1][j] == 0: BFS(h-1, j)

 

 

 

남은 빈 공간들의 둘레를 빼면, 필요한 조명 장식의 길이를 구할 수 있다.

import sys
from collections import deque
input = sys.stdin.readline

# 한 정육각형이 있을 때...
# 왼쪽 위 : (짝수) (y - 1, x - 1) 이 건물이 아닐 때 (홀수) (y, x - 1) 이 건물이 아닐 때
# 왼쪽 : (y - 1, x) 이 건물이 아닐 때
# 왼쪽 아래 : (짝수) (y - 1, x + 1) 이 건물이 아닐 때 (홀수) (y, x + 1) 이 건물이 아닐 때
# 오른쪽 위 : (짝수) (y, x - 1) (홀수) (y + 1, x - 1)
# 오른쪽 : (y + 1, x)
# 오른쪽 아래 : (짝수) (y, x + 1) (홀수) (y + 1, x + 1)

w, h = map(int, input().rstrip().split())
maps = [list(map(int, input().rstrip().split())) for _ in range(h)]

row_odd = [-1, -1, -1, 0, 1, 0]
col_odd = [-1, 0, 1, -1, 0, 1]
row_even = [0, -1, 0, 1, 1, 1]
col_even = [-1, 0, 1, -1, 0, 1]
result = 0
for i in range(h):
    for j in range(w):
        if maps[i][j] == 0: 
            continue
        for d in range(6):
            if i % 2 == 0:
                if not (0 <= i + col_even[d] < h and 0 <= j + row_even[d] < w and maps[i + col_even[d]][j + row_even[d]] == 1): 
                    result += 1
            else:
                if not (0 <= i + col_odd[d] < h and 0 <= j + row_odd[d] < w and maps[i + col_odd[d]][j + row_odd[d]] == 1): 
                    result += 1

# 외부에서 연결된 0 들을 전부 없애기
def BFS(y, x):
    global maps
    queue = deque()
    queue.append([y, x])
    maps[y][x] = 1

    while queue:
        now = queue.popleft()
        for d in range(6):
            if now[0] % 2 == 0:
                if 0 <= now[0] + col_even[d] < h and 0 <= now[1] + row_even[d] < w and maps[now[0] + col_even[d]][now[1] + row_even[d]] == 0:
                    maps[now[0] + col_even[d]][now[1] + row_even[d]] = 1
                    queue.append([now[0] + col_even[d], now[1] + row_even[d]])
            else:
                if 0 <= now[0] + col_odd[d] < h and 0 <= now[1] + row_odd[d] < w and maps[now[0] + col_odd[d]][now[1] + row_odd[d]] == 0:
                    maps[now[0] + col_odd[d]][now[1] + row_odd[d]] = 1
                    queue.append([now[0] + col_odd[d], now[1] + row_odd[d]])
# Left
for i in range(h):
    if maps[i][0] == 0: BFS(i, 0)
# Right
for i in range(h):
    if maps[i][w-1] == 0: BFS(i, w-1)
# Up
for j in range(w):
    if maps[0][j] == 0: BFS(0, j)
# Down
for j in range(w):
    if maps[h-1][j] == 0: BFS(h-1, j)

# 남은 0 들은 갇힌 공간. 옆면 지우기
for i in range(h):
    for j in range(w):
        if maps[i][j] == 0:
            for d in range(6):
                if i % 2 == 0:
                    if 0 <= i + col_even[d] < h and 0 <= j + row_even[d] < w and maps[i + col_even[d]][j + row_even[d]] == 1: 
                        result -= 1
                else:
                    if 0 <= i + col_odd[d] < h and 0 <= j + row_odd[d] < w and maps[i + col_odd[d]][j + row_odd[d]] == 1: 
                        result -= 1
print(result)