백준 5547 일루미네이션 Python - BFS풀이

BFS/DFS 를 응용한 그래프 탐색문제이다. 문제 조건에 대해 생각해볼 것들이 있는 문제여서 좋은 문제 같다 

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

5547번: 일루미네이션

1. BFS 탐색 기준 
처음에는 빌딩들을 기준으로 순회하고 외벽을 하나씩 세려고 했으나, 그 방법보다는 거꾸로 빈공간인 0을 탐색하고 1을 발견할 때마다 count를 해주는 방법이 적절하다.
위의 예시와 같이 (2,3) 같은 경우 빌딩을 기준으로 센다면, 6을 더하게 될 것이다. 

2. BFS 탐색 이전 그래프 마스킹하기 
0을 기준으로 탐색하기 위해서, 테두리를 0으로 마스킹이 필요하다. 
n, m 의 범위를 초과하는 경우에도 1과 인접하다면 카운트를 해주어야 하는데, 이런 경우를 고려한다면 배열을 (n+2) * (m+2) 크기로 늘려서 탐색하는 것이 낫다. 
또한 마스킹을 하면 bfs문을 한번만 실행시켜도, 0으로 모두 이어져있기 때문에 전체 그래프에 대한 탐색이 가능하다 

예제 1 입력을 마스킹한 모습

3. 정육각형 취급하기

문제에서 입력은 2차원 배열로 주어지지만, 우리가 평소에 생각하던 상하좌우 또는 대각선까지 포함한 8방향을 모두 탐색할 수 없다. 
정육각형이므로 총 6방향만 탐색할 수 있고, 탐색가능한 방향은 문제에서 짝수일때와 홀수일때 다르다고 힌트를 주고 있다. 

y좌표가 짝수/홀수인 경우 탐색가능한 6좌표 (정육각형 취급하기) 찾기

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

 

# 5547 일루미네이션
from collections import deque

m, n = map(int, input().split())
array = []
for i in range(n):
    array.append(list(map(int, input().split())))

answer = 0
visited = [[False] * (m+2) for _ in range(n+2)]

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

# 외곽 부분 0으로 마스킹
graph = [[0] * (m+2) for _ in range(n+2)]
for i in range(n):
    for j in range(m):
        graph[i+1][j+1] = array[i][j]

def bfs(y, x):
    queue = deque()
    queue.append((y, x))
    visited[y][x] = True
    count = 0
    while queue:
        y, x = queue.popleft()
        if y % 2 == 0: # 짝수일때
            for i in range(6):
                nx = x + dx[i]
                ny = y + dy[i]
                if nx < 0 or ny < 0 or nx >= m+2 or ny >= n+2:
                    continue
                # 0과 1이 연결되어 있으면 체크
                if graph[ny][nx] == 1:
                    count += 1
                elif graph[ny][nx] == 0 and not visited[ny][nx]:
                    queue.append((ny, nx))
                    visited[ny][nx] = True

        else:
            for i in range(6):
                nx = x + cx[i]
                ny = y + cy[i]
                if nx < 0 or ny < 0 or nx >= m+2 or ny >= n+2:
                    continue

                if graph[ny][nx] == 1:
                    count += 1
                elif graph[ny][nx] == 0 and not visited[ny][nx]:
                    queue.append((ny, nx))
                    visited[ny][nx] = True
    return count

print(bfs(0,0))

문제를 풀기위한 아이디어..! 0을 기준으로 탐색해야 한다는 것을 떠올리는 것이 key point가 되는 문제였다. 
그리고 헷갈렸던 점은 (y, x)라고 표기한다는 점이다. 
문제에서 "j번째 (1 ≤ j ≤ w) 정수의 좌표는 (j, i)이며" 이라고 주어졌는데 이를 주의깊게 읽지 않아서 계속 틀린 값이 나왔다.