[boj] 5547_일루미네이션_python

문제링크

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

5547번: 일루미네이션

---

문제설명

문제

입력

두 개의 정수 W와 H . (1 ≤ W, H ≤ 100) 

W*H 상근이네 집의 건물 배치  ( 건물이 있을 때는 1이고, 없을 때는 0이다. 주어지는 입력에는 건물이 적어도 하나 있다. )

 

출력

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

 

조건

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

---

문제풀이

 

조건

가장 왼쪽의 좌표 (1,1)에서 시작

(x,y)의 오른쪽에 있는 정육각형의 좌표는 (x + 1, y)

y가 홀수일 때, 아래쪽에 있는 정육각형의 좌표는 (x, y+1)

y가 짝수일 때, 오른쪽 아래에 있는 정육각형의 좌표는 (x, y+1)

좌표 설명

예) y가 홀수 : 3,3를 기준으로 x=3, y=3라고 했을 때,

(3,2),  (4,2),  (4,3),  (4,4),  (3,4),  (2,3)

(x-1,y), (x,y-1), (x+1, y), (x+1, y+1), (x, y+1), (x-1, y+1) 

(-1,0), (0,-1), (1,0), (1,1), (0,1), (-1, 1)

 

예) y가 짝수 : 2,2를 기준으로 x=2, y=2라고 했을 때,

(1,1), (2,1), (3,2), (2,3), (1,3), (1,2)

(x-1,y-1), (x,y-1), (x+1, y+1), (x, y+1), (x-1, y+1), (x-1, y) 

(-1,-1), (0,-1), (1,-1), (1,0), (0,1), (-1, 0)

---

 

해당하는 부분을

위에 작성해준 것처럼

각각 dy와 dx처럼 표현해준다

---

# 일루미네이션
# 풀이시간 : 6h
# 공간 복잡도 O(2*(X+2)(Y+2))=> O(XY)
# 시간 복잡도 O(XY)

import sys
from collections import deque
input = sys.stdin.readline
odd = [[-1,0], [0,-1], [1,0], [1,1], [0,1], [-1, 1]] # y가 홀수일 때
even = [[-1,-1], [0,-1], [1,-1], [1,0], [0,1], [-1, 0]] # y가 짝수일 때
X, Y = map(int, input().split()) # 좌표 받기
illumination = [[0 for _ in range(X+2)] for _ in range(Y+2)] # 집 좌표 기록
outRange = [[False for _ in range(X+2)]for _ in range(Y+2)] # 바깥인 경우 기록
for i in range(1, Y+1): # 맨 끝 부분을 비워둔다.
    lst = list(map(int, input().split()))
    for j in range(1, X+1):
        illumination[i][j] = lst[j-1]

Q = deque([[0,0]])

while Q:
    y, x = Q.popleft()
    for k in range(6):
        if y % 2 == 0: # 짝수일 때
            dy, dx = y + even[k][0], x + even[k][1]
            if 0<= dy < Y+2 and 0<= dx < X+2:
                if outRange[dy][dx] == False and illumination[dy][dx] == 0:
                    outRange[dy][dx] = True
                    Q.append([dy, dx])
        else: # 홀수일 때
            dy, dx = y + odd[k][0], x + odd[k][1]
            if 0<= dy < Y+2 and 0<= dx < X+2:
                if outRange[dy][dx] == False and illumination[dy][dx] == 0:
                    outRange[dy][dx] = True
                    Q.append([dy, dx])
res = 0
dy, dx =0,0
for i in range(1, Y+1):
    for j in range(1, X+1):
        if illumination[i][j] == 0: continue
        for k in range(6):
            if i % 2 == 0:
                dy, dx = i + even[k][0], j + even[k][1]
            else:
                dy, dx = i + odd[k][0], j + odd[k][1]
            if outRange[dy][dx]: res +=1
print(res)

---

참고 레퍼런스

1. https://velog.io/@paulus0617/boj5547

[백준] 5547번: 일루미네이션