백준 5547 일루미네이션 Python - BFS풀이
BFS/DFS 를 응용한 그래프 탐색문제이다. 문제 조건에 대해 생각해볼 것들이 있는 문제여서 좋은 문제 같다
https://www.acmicpc.net/problem/5547
5547번: 일루미네이션
첫째 줄에 두 개의 정수 W와 H가 주어진다. (1 ≤ W, H ≤ 100) 다음 H줄에는 상근이네 집의 건물 배치가 주어진다. i+1줄에는 W개의 정수가 공백으로 구분되어 있다. j번째 (1 ≤ j ≤ w) 정수의 좌표는
www.acmicpc.net
1. BFS 탐색 기준
처음에는 빌딩들을 기준으로 순회하고 외벽을 하나씩 세려고 했으나, 그 방법보다는 거꾸로 빈공간인 0을 탐색하고 1을 발견할 때마다 count를 해주는 방법이 적절하다.
위의 예시와 같이 (2,3) 같은 경우 빌딩을 기준으로 센다면, 6을 더하게 될 것이다.
2. BFS 탐색 이전 그래프 마스킹하기
0을 기준으로 탐색하기 위해서, 테두리를 0으로 마스킹이 필요하다.
n, m 의 범위를 초과하는 경우에도 1과 인접하다면 카운트를 해주어야 하는데, 이런 경우를 고려한다면 배열을 (n+2) * (m+2) 크기로 늘려서 탐색하는 것이 낫다.
또한 마스킹을 하면 bfs문을 한번만 실행시켜도, 0으로 모두 이어져있기 때문에 전체 그래프에 대한 탐색이 가능하다
3. 정육각형 취급하기
문제에서 입력은 2차원 배열로 주어지지만, 우리가 평소에 생각하던 상하좌우 또는 대각선까지 포함한 8방향을 모두 탐색할 수 없다.
정육각형이므로 총 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)이며" 이라고 주어졌는데 이를 주의깊게 읽지 않아서 계속 틀린 값이 나왔다.