[Python] 백준 5527 일루미네이션

문제 링크 : https://www.acmicpc.net/problem/5547

5547번: 일루미네이션

 

1. 접근 방법

BFS를 응용하여 해결하는 문제인데, 육각형 구조에 따라 추가적인 고려사항이 생긴 문제이다.

그리고 단순히 육각형의 수를 원하는 것이 아니라 모서리의 길이를 구하여야 하므로, 조금 더 복잡한 과정이 필요할 수 있다.

 

처음에는 각 선분을 좌표로 하여 탐색하려 했다. 어차피 한붓그리기 형태가 될 것이므로 구현은 조금 복잡할 수 있지만, 쉽게 구할 수 있을 것 같았다. 하지만, 방문 확인하는 것과 문제에서 주어진 첫 번째 예시처럼 내부의 공간이 있을 때 잡아내지 못할 것 같았다.

그다음에는 각각 덩어리를 구하여 외부 선분을 찾으려 했는데, 이 경우는 배치되는 모양에 따라 많이 복잡해질 수 있을 것 같았다.

 

그래서 건물(1)을 확인하는 대신 빈 공간(0)을 확인하여 벽의 수를 구했다.

---

2. 풀이 코드

🖥python 코드 링크 : https://github.com/mintropy/PS/blob/master/BAEKJOON/Python/5000/5500/5547.py

GitHub - mintropy/PS: 다양한 알고리즘 문제 풀이 저장소입니다.

📕코드 해설

앞서 이 문제를 해결하기 위한 두가지 방법을 소개하면 다음과 같다.

첫 번째는 탐색방법이다. 우선 문제에서 주어진 것과 좌표를 다른 방향으로 두어 계산했는데, 이는 큰 문제는 되지 않을 것 같다.

이때, 위에서부터 짝수, 홀수 줄에 따라 6방향 탐색을 살펴보면, 좌표의 변환이 다르다. 그래서 위에서부터 몇 번째 줄이냐에 따라 탐색을 다르게 해야 한다. 따라서 다음과 같이 델타를 설정했다.

delta = [
    [(-1, 0), (0, 1), (1, 0), (1, -1), (0, -1), (-1, -1)],
    [(-1, 1), (0, 1), (1, 1), (1, 0), (0, -1), (-1, 0)],
]

 

다음으로 빨간색이 건물, 파란색이 빈 공간이라 할 때, 벽을 탐색하는 과정이다.

각 위치에서 인접한 건물의 개수를 파악한다. 예를 들어 (1,1)에서 1개, (1,2)에서 2개와같은 방식이다. 그리고 이 인접한 건물의 수에 따라 벽의 수가 정해 지므로, 이 숫자들을 누적하여 기록해두면 된다.

그런데 만약 (2,1)이나 (1,3)처럼 가장 바깥부분이 건물이면 어떻게 처리하면 좋을까? 그래서 외부에 0으로 패딩을 두고 탐색했다.

walls = (
    [[0] * (W + 2)] + [[0] + list(MIIS()) + [0] for _ in range(H)] + [[0] * (W + 2)]
)

 

각 위치별 육각형 탐색과, 벽의 개수 탐색 두부분을 적절히 활용하면 문제를 해결할 수 있다.

 

queue = deque([(0, 0)])
while queue:
    x, y = queue.popleft()
    if visited[x][y]:
        continue
    visited[x][y] = True
    ans += count_walls(x, y)
    count[x][y] = count_walls(x, y)
    for dx, dy in delta[x % 2]:
        nx, ny = x + dx, y + dy
        if 0 <= nx <= H + 1 and 0 <= ny <= W + 1:
            if not walls[nx][ny]:
                queue.append((nx, ny))

deque를 하나 선언하여, 가장 외부에서 시작했다. 어차피 벽은 외부와 연결돼있을 것이라 생각하여 패딩 한 부분에서 시작을 했고, 추가적인 조건문이나 탐색과정을 생략 할 수 있다.

 

def count_walls(x: int, y: int) -> int:
    global walls, delta
    count = 0
    for dx, dy in delta[x % 2]:
        nx, ny = x + dx, y + dy
        if 0 <= nx <= H + 1 and 0 <= ny <= W + 1:
            if walls[nx][ny]:
                count += 1
    return count

벽의 개수는 6방향 탐색을 통하여 해결했다.

---

3. 생각 정리

육각형 탐색의 몇몇 문제를 보았는데, 이 문제는 모서리의 길이를 구하는 것이라 조금 고민했다. 같은 방식을 사용한다면 사각형 등의 경우도 유사하게 해결할 수 있을 것 같다.