[알고리즘] 백준5547 일루미네이션 - 파이썬

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

5547번: 일루미네이션

 

 

[초기 접근 방식]

• 모든 건물을 '6'으로 초기화한 배열을 하나 생성한다. 그리고 회색 건물('1')만을 탐색하면서 연결된 회색 건물이 있을 때마다 6으로 초기화한 배열에 해당 건물을 -1을 해준다. 여기서 주의할 점은 정육각형의 범위로 이동해야 하지만 짝수 줄과 홀수 줄에 따라 이동 범위가 다르기 때문에 이동거리를 설정한 배열 dy, dx를 잘 설정해줘야 한다.
• 위와 같이 코드를 작성했지만 회색건물로 둘러싸인 건물이 없는 부분을 해결하지 못했다. 이 부분도 bfs로 탐색해야 했을까 싶기도 하다.

[다른 사람의 풀이]

출처는 코드를 공개로 해주신 kywoo26님이 작성한 답을 보았다.

• 주어진 지도의 가로, 세로폭을 +2 씩 한다. 흰색 부분('0')으로 둘러싸이게 지도를 초기화한다.
• 좌표(0,0)부터 시작해서 정육각형 범위로 탐색을 하면서 회색 건물을 만나면 카운트한다.
• 역시나 주의할점은 짝수, 홀수 줄에 따라 정육각형의 범위가 달라진다는 점
• 핵심은 회색건물('1')을 탐색하는 것이 아닌 주변 흰색 부분('0')을 탐색한다는 점이다. 이렇게 풀이하면 회색 건물('1)에 둘러싸인 흰색 부분('0')을 탐색하지 않기 때문에 초기 접근 방식에서 해결하지 못한 점을 해결할 수 있다.
• 위 그림은 직접 bfs탐색 순서를 지키지 않았지만 직접 갯수를 세보면서 이해를 했다.

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

w, h = map(int, input().split())
graph = [[0 for _ in range(w+2)] for _ in range(h+2)] # +2씩 해준다. 외밖과 닿는 면을 다 흰색정육각형으로 둘러준다.
for i in range(1, h+1):
    graph[i][1:w+1] = map(int, input().split())

dy = [0, 1, 1, 0, -1, -1]
dx = [[1, 0, -1, -1, -1, 0], [1, 1, 0, -1, 0, 1]] # 짝수줄, 홀수줄 범위내 이동거리 설정

def bfs(y, x):
    queue = deque()
    queue.append((y, x))
    visited = [[False for _ in range(w+2)] for _ in range(h+2)] # 방문체크 배열 생성
    visited[y][x] = True
    cnt = 0
    while queue:
        y, x = queue.popleft()

        for i in range(6):
            yy = y + dy[i]
            xx = x + dx[y % 2][i]
            if 0 <= yy < h+2 and 0 <= xx < w+2:
                if graph[yy][xx] == 0 and not visited[yy][xx]:
                    queue.append((yy, xx))
                    visited[yy][xx] = True
                elif graph[yy][xx] == 1:
                    cnt += 1
    return cnt

print(bfs(0, 0))