Notion에서 작성한 글이라, 여기에서 더 깔끔하게 보실 수 있습니다! 😮😊

---

[Challenger] 일루미네이션

[일루미네이션]

접근 과정

• 처음 문제를 읽고는, 연결 요소의 개수와 연결 요소를 구성하는 노드의 수를 구해서 상황에 따라 $6$을 곱해주고 몇을 곱해주고 더해주는 방식을 생각해 보았다.
  • 하지만 이 정보들만으로 벽의 길이를 계산하는 것은 불가능했다. 인접한 노드들의 0 또는 1 개수까지 하나하나 체크해본다면 어떻게 해볼 수도 있을 것 같았지만 너무 복잡해 보여서 다른 방법을 고민해 봤다.
• 격자 형태의 문제에서 BFS를 돌릴 때, 인접한 노드로 각 변을 따라 퍼져나가듯 탐색하는 장면이 머리에 그려지면서 문제 해결의 실마리가 보였다.
• BFS를 돌리면서, 한 노드에서 다른 노드로 이동할 때 지도에서 0과 1이 맞닿는 부분의 개수를 세어주면 되는 문제로 바뀌었다. 여기에서 추가로 생각할 점이 두 가지 있다. Point 1. 지도의 위, 아래, 왼쪽, 오른쪽 끝에 건물이 위치한 경우, 그 벽의 개수를 어떻게 세어줄 수 있을지 Point 2. 건물 내부에 빈 공간이 있는 경우 이 벽에는 조명을 장식하지 않는데, 이 부분 또한 0과 1이 맞닿는 부분이라, 이를 어떻게 해결할지
  

Point 1. 지도의 테두리에 건물이 위치한 경우

• 두 가지 방법을 생각해 보았다.
  1. 지도의 테두리를 모두 0으로 둘러준 다음 BFS
     • 장점 : 벽면의 길이의 합을 한 번의 BFS로 계산할 수 있음(Flood Fill) → 직관적
     • 단점 : (사실 이 정도는 괜찮지만) 메모리 사용량 증가
     • 예상 시간복잡도 : BFS $O((W+2)(H+2))$
  2. 현재 상태 그대로 BFS를 돌린 다음, 지도의 테두리에 위치한 벽의 수는 따로 계산
     • 장점 : 메모리 사용량 감소
     • 단점 : Flood Fill이 불가능하기 때문에 지도를 순회하며 방문하지 않은 노드에 대해 여러 번의 BFS 필요, 상대적으로 복잡해짐
     • 예상 시간복잡도 : 순회 $O(2W+2H)$, BFS $O(WH)$

Point 2. 건물 내부에 빈 공간이 있는 경우

• 이 빈 공간을 어떻게 처리할지 고민하는 데에 시간을 꽤 소모했다. 의식의 흐름을 적어보면,
• 매 노드마다 1로 둘러쌓여있는지 $O(WH)$로 체크해주고 빼야 하나…? 그런데 빈 공간 내부에서 또 BFS를 돌려서 빼야 할 것 같다!
• BFS를 마치고도 건물을 제외한 노드가 방문하지 않은 노드일 경우 빈 공간이라고 볼 수 있겠다! 그런데 이 빈 공간 내부에서 또 BFS를 돌려야 해서 복잡할 것 같다…
• 중요한 것은 “외벽에서” 0과 1이 맞닿는 부분이기 때문에, 0을 기준으로 BFS를 돌리고, 1인 부분의 값을 변경하지만 않으면 자연스럽게 외벽만 고려할 수 있겠다!

Solution 1. 테두리를 0으로 둘러준 다음 BFS $O((W+2)(H+2))$

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

def bfs(i, j):
    queue = deque([(i, j)])
    hexa[i][j] = 2
    cnt = 0

    delta = (((0, -1), (0, 1), (-1, -1), (-1, 0), (1, -1), (1, 0)),
             ((0, -1), (0, 1), (-1, 0), (-1, 1), (1, 0), (1, 1)))
    
    while queue:
        y, x = queue.popleft()
        for dy, dx in delta[y%2]:
            ny, nx = y+dy, x+dx

            if 0<=ny<h+2 and 0<=nx<w+2 and hexa[ny][nx] <= 1:
                if hexa[ny][nx] == 1:
                    cnt += 1
                else:
                    hexa[ny][nx] = 2
                    queue.append((ny, nx))
                
    return cnt

w, h = map(int, input().split())
hexa = [[0]*(w+2)] + [[0]+[*map(int, input().split())]+[0] for _ in range(h)] + [[0]*(w+2)]
print(bfs(0, 0))

• 다음 노드에 대해 위 또는 아래로 탐색을 할 때 짝수번째 행에서의 탐색 방향과 홀수번째 행에서의 탐색 방향이 다르므로 이를 각각 따로 지정해주었다.
• 지도의 기존 값이 1인 경우 이는 벽에 해당하므로 cnt를 증가시킨다.
• 지도의 기존 값이 0인 경우 방문처리를 위해 2로 바꿔준다. (숫자 2가 갖는 의미는 방문했다는 의미 외에 다른 의미를 갖지 않는다. visited와 같은 방문처리용 리스트를 사용하지 않아 메모리를 절약하기 위함이다!)

Solution 2. 그대로 BFS + 테두리 따로 계산 $O(WH+2W+2H)$

---