[Python] 2234 성곽

[Gold III] 성곽 - 2234 

[문제 링크](https://www.acmicpc.net/problem/2234)

---

💻 문제 정의

 

다음과 같은 그림처럼 생긴 성곽이 있다. 굵은 선은 벽이고 점선은 벽이 없는 통로다. 이러한 형태의 성의 지도를 입력받았을 때, 다음을 구하자.

1. 이 성에 있는 방의 개수
2. 가장 넓은 방의 넓이
3. 하나의 벽을 제거하여 얻을 수 있는 가장 넓은 방의 크기

서쪽에 벽이 있을 때는 1을, 북쪽에 벽이 있을 때는 2를, 동쪽에 벽이 있을 때는 4를, 남쪽에 벽이 있을 때는 8을 더한 값이 주어진다.

💡 접근 및 설계

비트마스킹을 이용하여 현재 칸에서 4방향 중 어느 방향에 벽이 있는지 판단, 벽이 없는 방향으로 이동(BFS)하여 방 하나의 크기를 구할 수 있게 된다. BFS 호출 횟수가 방의 개수가 될 것이다.

벽 하나를 제거하여 얻을 수 있는 가장 넓은 방의 크기는, 각 방의 고유 아이디를 부여하여 아이디가 달라지는 지점의 벽을 기준으로 두 방의 크기의 합을 업데이트하여 최댓값을 구한다.

✏️ 알고리즘 풀이

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

visited = [[0] * N for _ in range(M)]
room_size = {}
room_id = 0

def bfs(x, y, room_id):
    Q = deque()
    Q.append([x, y])
    visited[x][y] = room_id
    cnt = 1

    while Q:
        x, y = Q.popleft()

        for i in range(4):
            # 벽이 존재하는지 체크
            if matrix[x][y] & (1 << i):
                continue

            # 벽이 없는 방향으로 이동
            nx = x + dx[i]
            ny = y + dy[i]
            
            if 0 <= nx < M and 0 <= ny < N and visited[nx][ny] == 0:
                visited[nx][ny] = room_id
                Q.append([nx, ny])
                cnt += 1

    return cnt
    
# 방의 개수 및 각 방의 크기 찾기
for i in range(M):
    for j in range(N):
        if visited[i][j] == 0:
            room_id += 1
            room_size[room_id] = bfs(i, j, room_id)

너비 우선 탐색 코드다. visited에는 room_id가 저장될 것이다. BFS함수의 반환값은 탐색 횟수, 즉 방의 크기가 될 것이고, BFS함수 호출 횟수는 방의 개수가 될 것이다.

# 벽이 존재하는지 체크
  if matrix[x][y] & (1 << i):
	  continue

오늘의 핵심 코드다. 1, 4, 8 16은 이진수로 0001, 0010, 0100, 1000으로 표현할 수 있다.

다음의 코드는 1을 i비트 만큼 왼쪽으로 shift한다. 따라서 1 → 10 → 100 → 1000 식으로 표현될 것이다. 만약 남쪽에 문이 있을 경우, 16 & (1 << 4) → 16 & 1000 → 1000 & 1000 → True가 되므로 벽이 있다는 것을 알 수 있다.

merge_room_size = 0
# 방 아이디가 서로 다른 방끼리 맞닿은 벽을 허물었을 때 크기
for x in range(M):
    for y in range(N):
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < M and 0 <= ny < N:
                # 현재 방 아이디와 이동 후 방 아이디가 다르다면,
                if visited[x][y] != visited[nx][ny]:
                    a = room_size[visited[x][y]]
                    b = room_size[visited[nx][ny]]
                    # 두 방의 크기를 더해서 merge_room_size와 비교하여 큰 값 저장
                    merge_room_size = max(merge_room_size, a + b)

마지막으로 서로 다른 방 끼리 맞닿은 벽을 허물었을 때 방의 크기를 구해 최댓값을 업데이트 한다.

🗒️ 최종 제출 코드

# 2234 성곽

from collections import deque

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

def bfs(x, y, room_id):
    Q = deque()
    Q.append([x, y])
    visited[x][y] = room_id
    cnt = 1

    while Q:
        x, y = Q.popleft()

        for i in range(4):
            # 벽이 존재하는지 체크
            if matrix[x][y] & (1 << i):
                continue

            # 벽이 없는 방향으로 이동
            nx = x + dx[i]
            ny = y + dy[i]
            
            if 0 <= nx < M and 0 <= ny < N and visited[nx][ny] == 0:
                visited[nx][ny] = room_id
                Q.append([nx, ny])
                cnt += 1

    return cnt

N, M = map(int, input().split())

matrix = []
for _ in range(M):
    matrix.append(list(map(int, input().split())))

visited = [[0] * N for _ in range(M)]
room_size = {}
room_id = 0

# 방의 개수 및 각 방의 크기 찾기
for i in range(M):
    for j in range(N):
        if visited[i][j] == 0:
            room_id += 1
            room_size[room_id] = bfs(i, j, room_id)

merge_room_size = 0
# 방 아이디가 서로 다른 방끼리 맞닿은 벽을 허물었을 때 크기
for x in range(M):
    for y in range(N):
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < M and 0 <= ny < N:
                # 현재 방 아이디와 이동 후 방 아이디가 다르다면,
                if visited[x][y] != visited[nx][ny]:
                    a = room_size[visited[x][y]]
                    b = room_size[visited[nx][ny]]
                    # 두 방의 크기를 더해서 merge_room_size와 비교하여 큰 값 저장
                    merge_room_size = max(merge_room_size, a + b)

print(len(room_size))
print(max(room_size.values()))
print(merge_room_size)

---

💭 오늘의 회고

비트마스킹에 대해 자세히 알 게 되었다. 파이썬에서 정수형은 이진수로 자동 매핑이 되어 비트마스킹이 쉽게 가능하다는 것을 알게 되었다.