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

2022. 8. 31. 09:56

문제 링크 #

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

문제 해설 #

Idea #

전체 좌표 평면의 외곽에 1만큼의 여백을 추가하고 x,y 좌표가 0부터 시작한다고 판단
y가 홀수 일 때, 인접한 좌표는 상하좌우와 함께 우상단,우하단을 포함
y가 짝수 일 때, 인접한 좌표는 상하좌우와 함께 좌상단, 좌하단을 포함
건물이 없는 좌표를 BFS 탐색하면서 건물과 만나는 지점을 카운트

Time Complexity #

BFS: O(N^2) = 10,000

Data Size #

W, H: 1 <= int <= 100

해설 코드 #

python

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

W, H = map(lambda x: int(x)+2, input().split())
maps = [[0] * W for _ in range(H)]
for i in range(1,H-1):
    maps[i] = [0]+list(map(int, input().split()))+[0]
visited = [[False] * W for _ in range(H)]

def bfs(start):
    queue = deque([start])
    dy = [0,1,0,-1,1,-1]
    cnt = 0

    while queue:
        y,x = queue.popleft()
        dx = [-1,0,1,0,-1,-1] if y%2==0 else [-1,0,1,0,1,1]
        for i in range(6):
            ny, nx = y+dy[i], x+dx[i]
            if 0<=ny<H and 0<=nx<W:
                if maps[ny][nx] == 0 and not visited[ny][nx]:
                    queue.append((ny,nx))
                    visited[ny][nx] = True
                elif maps[ny][nx] == 1:
                    cnt += 1
    return cnt

visited[0][0] = True
print(bfs((0,0)))