[백준 5547번] 일루미네이션 (python)

문제

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

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

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

 

기록

(graph 4일차) 오랜만에 구글링 안하고 풀었다!

 

건물의 바깥쪽 테두리만 필요했기 때문에, 바깥쪽 칸의 0칸과 연결된 칸만 탐색하며 모서리 개수를 셌다. 추가로 바깥쪽 1칸은 아래 규칙에 맞게 모서리개수를 셌다.

 

코드

import sys
input = sys.stdin.readline

m, n = map(int, input().split())
board = [list(map(int, input().split())) for i in range(n)]
visit = [[0]*m for i in range(n)]

# 연결된 0인 칸 탐색 후 테두리 개수 반환
def dfs(y, x):
    stack = [(y, x)]
    visit[y][x] = 1
    cnt = 0
    while stack:
        y, x = stack.pop()
        if y%2 : di = [(-1,0), (-1,-1), (0,-1), (0,1), (1,0), (1,-1)]
        else : di = [(-1,0), (-1,1), (0,-1), (0,1), (1,0), (1,1)]
        for i, j in di:
            if y+i>=0 and y+i<n and x+j>=0 and x+j<m and not visit[y+i][x+j]:
                if board[y+i][x+j] : cnt+=1
                else :
                    visit[y+i][x+j] = 1
                    stack.append((y+i, x+j))
    return cnt

# 가장 바깥쪽 칸들과 연결된 칸 탐색
total = 0
for y in [0, n-1]: # 맨 위, 맨 아래 줄 탐색
    for x in range(m):
        if board[y][x] :
            total += 2
            if (y==0 and x==m-1) or (y==n-1 and x==0):
                total -= 1
        elif board[y][x]==0 and not visit[y][x]:
            total += dfs(y, x)
for y in range(n): # 맨 오른쪽, 맨 왼쪽 줄 탐색
    for x in [0, m-1]:
        if board[y][x] :
            if (x==0 and y%2) or (x==m-1 and y%2==0) : total +=3
            else : total += 1
        elif board[y][x]==0 and not visit[y][x]:
            total += dfs(y, x)
            
print(total)

1. 입력값 저장

2. dfs로 인접한 0인 칸 탐색하는 함수 구현

3. 맨 위, 맨 아랫줄 탐색하며 0인 칸이면 dfs로 탐색하여 벽면 개수 더하기, 1인 칸이면 규칙에 맞게 벽면 개수 더하기

4. 맨 오른쪽, 맨 왼쪽줄 탐색하며 위와 같이 0인 칸일 때와 1인 칸일 때를 나눠 벽면 개수 더하기

5. 최종 벽면개수 출력