[BOJ] 5547 일루미네이션

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

육각형 모양으로 배열되는 건물들이 있는데 밖에서 볼 수 있는 부분만 조명을 달려고 하는데 밖에서 볼 수 있는 부분의 길이가 얼마나 되는지 구하는 문제이다.

예전에 빙산 문제나 치즈 문제랑 비슷한 결인 것 같아서 비슷하게 접근했다.

규칙

일단 y좌표에 따라서 위아래로 접하는 칸의 x좌표가 달라졌다.

y좌표가 홀수이면 위아래로 접하는 칸의 x좌표는 x, x+1이되고
y좌표가 짝수이면 위아래로 접하는 칸의 x좌표는 x-1, x가 된다.

이것을 이용해서 dy, dx를 정의했다.

dy = [0, 0, 1, 1, -1, -1]

# 홀수용 dx 좌우 하 상
dxo = [1, -1, 1, 0, 1, 0]
# 짝수용
dxe = [1, -1, -1, 0, -1, 0]

그리고 밖이랑 안이랑 구분시켜주기 위해서 입력으로 받은 배열의 테두리에 0을 추가해줬다.

house = [[0] * (w+2)]
house += [[0] + list(map(int, input().split())) + [0] for _ in range(h)]
house.append([0] * (w+2))

w += 2
h += 2

그리고 테두리와 연결된 "밖"이라고 판단되는 부분을 5로 덮어주었다.

que = [(0, 0)]
idx = 0
house[0][0] = 5

while idx < len(que):
  y, x = que[idx]
  idx += 1
  
  for d in range(6):
    ny = y + dy[d]
    nx = x + (dxo[d] if y%2 else dxe[d])
    
    if 0 <= ny < h and 0 <= nx < w and house[ny][nx] == 0:
      house[ny][nx] = 5
      que.append((ny, nx))

5로 한거는 출력할 때 0과 1사이에서 그나마 구분하기 쉬울 것 같아서 5로 했다.

마지막으로는 배열 전체를 탐색하면서 1을 만나면 거기부터 BFS를 시작해서 1과 연결된 부분을 0으로 처리해주었다.
테두리 길이는 1을 만났을 때 6을 더해주고, BFS로 탐색하면서 0이나 1을 만나면 1씩 빼주는 식으로 처리했다.

전체 코드

# y좌표가 짝수면 x-1, x
# y좌표가 홀수면 x, x+1


w, h = map(int, input().split())

house = [[0] * (w+2)]
house += [[0] + list(map(int, input().split())) + [0] for _ in range(h)]
house.append([0] * (w+2))

w += 2
h += 2

dy = [0, 0, 1, 1, -1, -1]

# 홀수용 dx 좌우 하 상
dxo = [1, -1, 1, 0, 1, 0]
# 짝수용
dxe = [1, -1, -1, 0, -1, 0]

que = [(0, 0)]
idx = 0
house[0][0] = 5

while idx < len(que):
  y, x = que[idx]
  idx += 1
  
  for d in range(6):
    ny = y + dy[d]
    nx = x + (dxo[d] if y%2 else dxe[d])
    
    if 0 <= ny < h and 0 <= nx < w and house[ny][nx] == 0:
      house[ny][nx] = 5
      que.append((ny, nx))
      
ans = 0
for i in range(h):
  for j in range(w):
    
    if house[i][j] == 1:
      wall = 0
      que = [(i, j)]
      idx = 0
      house[i][j] = 0
      while idx < len(que):
        y, x = que[idx]
        idx += 1
        wall += 6
        
        for d in range(6):
          ny = y + dy[d]
          nx = x + (dxo[d] if y%2 else dxe[d])
          
          # 다음 건물이랑 붙어 있으면 que에 추가하고 wall 값 하나 빼기
          if 0 <= ny < h and 0 <= nx < w and house[ny][nx] == 1:
            house[ny][nx] = 0
            que.append((ny, nx))
            wall -= 1
          # 이미 지나온 건물이라 0 혹은 건물로 둘러 쌓여진 부분이라 0이라서 wall 하나 빼기
          elif 0 <= ny < h and 0 <= nx < w and house[ny][nx] == 0:
            wall -= 1
      ans += wall
      

print(ans)