[백준] 5547 일루미네이션

💻 문제

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

💻 내 코드

import sys
from collections import deque

w, h = map(int, sys.stdin.readline().split())

wall = [[0]*(w+2) for _ in range(h+2)]

for i in range(1, h+1): # 위, 아래, 왼쪽, 오른쪽을 0으로 채워줌
    wall[i][1:w+1]=map(int, sys.stdin.readline().split())

dx = [-1,-1,0,0,1,1]
dy=[[0,1,-1,1,0,1],[-1,0,-1,1,-1,0]] # 홀수 , 짝수

res = 0
queue = deque([])
visited = [[False] * (w + 2) for _ in range(h + 2)]
queue.append((0, 0))
visited[0][0] = True

while queue:
    x, y = queue.popleft()

    for i in range(6):
        nx = x + dx[i]
        if x % 2 == 1:
            ny = y + dy[0][i]
        else:
            ny = y + dy[1][i]

        if 0<=nx<h+2 and 0<=ny<w+2:
            if wall[nx][ny]==0 and not visited[nx][ny]: # 만약 0이고 아직 방문하지 않았다면
                visited[nx][ny]=True
                queue.append((nx, ny))
            elif wall[nx][ny]==1: # 만약 1이라면
                res+=1 # 결과 더해주기
print(res)

💡 풀이

• 1이 0과 닿는 곳을 확인해준다
• 각 변이 닿는 곳을 확인해보면 홀수번째 줄과 짝수번째 줄이 각각 다르게 닿음
• 행이 짝수일때와 홀수일때를 비교해서 BFS 탐색 범위 지정해줌
• 효과적인 탐색을 위해 가장자리를 0으로 채워준다
• 가장자리에서부터 탐색하다가 만약 1을 만나면 결과+1을 해주고 0을 만나면 큐에 넣어 계속 탐색할 수 있도록 함
  - 이렇게 해야 1로 둘러쌓인 0은 제외하고 결과를 얻을 수 있다