[백준 / Python 파이썬] 5547번 - 일루미네이션

[Gold IV] 일루미네이션 - 5547

---

문제 링크

분류

그래프 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색

문제 설명

부유한 집안의 상속자 상근이네 집은 그림과 같이 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)이다.

출력

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

---

from collections import deque
import sys

input = sys.stdin.readline
dr = [0, 1, 1, 0, -1, -1]
dc = [[1, 0, -1, -1, -1, 0], [1, 1, 0, -1, 0, 1]]

W, H = map(int, input().split())
wall = [0] * (W + 2)
graph = [wall] + [[0] + list(map(int, input().split())) + [0] for _ in range(H)] + [wall]

def BFS(r, c):
    queue = deque()
    queue.append((r, c))
    visited = [[0] * (W + 2) for _ in range(H + 2)]
    visited[r][c] = 1
    answer = 0

    while queue:
        r, c = queue.popleft()
        for d in range(6):
            nr = r + dr[d]
            nc = c + dc[r % 2][d]
            if 0 <= nr < H + 2 and 0 <= nc < W + 2:
                if graph[nr][nc] == 0 and visited[nr][nc] == 0:
                    visited[nr][nc] = 1
                    queue.append((nr, nc))
                elif graph[nr][nc] == 1:
                    answer += 1

    return answer

result = BFS(0, 0)
print(result)