[BFS] 백준 2234 : 성곽 - 파이썬 Python

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

2234번: 성곽

 

생각하기

각 칸의 테두리를 기준으로 구역을 나누는 것이므로 

각 칸을 돌면서 해당 칸이 구역에 속하는지, 속하지 않는지를 판단하면 되는 방법이라고 생각했다

 

BFS를 사용하여 칸들을 돌아보기로 했다

 

세가지 문제에 대한 답을 풀어야 하는데

1. 성에 있는 방의 개수

각 칸에 대한 BFS를 돌면서 더이상 갈 곳이 없으면 방의 개수를 증가시킨다

 

2. 가장 넓은 방의 넓이 

1번의 방법을 수행하면서 BFS를 돌면서 갈 수 있는 칸의 개수를 세고 방의 개수를 증가시킬 떄, max 처리를 통해 구한다

 

3. 하나의 벽을 제거하여 얻을 수 있는 가장 넓은 방의 크기

제일 어려웠던 부분이었다

각 방을 구하고 나서 M*N의 배열에 방에 해당하는 영역 방 크기를 넣어주었다

M*N을 하나씩 다시 돌면서 벽이 있는 경우 해당 벽 옆의 칸에 크기가 있는 경우 해당 크기와 합쳐준 값을 max 처리 통해 구한다

사실 내가 이렇게 써놓고도 무슨 말을 하는 것인지 모르겠지만 코드를 통해 이해하자

정리하자면 아래 두가지를 고려해주어야 한다

• 현재 칸의 벽과 마주한 이웃칸에 들어있는 크기를 현재 칸이 속한 구역과 더한다
• 현재 칸의 벽과 마주한 이웃칸에 들어있는 크기가 존재하는지 ( 아직 방이라는 것을 살펴보았는지 )
• 현재 칸의 벽과 마주한 이웃칸이 현재 칸이 속한 구역과 같은 구역이 아닌지 확인해야

 

구현하기

space class

동서남북 멤버 변수를 두어서 해당 칸에서 벽이 어디에 있는지 클래스로 나타낸다

 

set_space_dir 메소드

입력값(10진수)를 2진수 str값으로 변환시킨후 해당 값을 파싱하여 

해당 칸의 동서남북 어디에 벽이 있는지 세팅한다

 

visited_total 배열

같은 구역의 칸은 해당 구역의 크기가 들어있는 배열

해당 배열로 추후 3번을 구할 수 있다

 

room_cnt

BFS를 돓면서 q가 비면 -> 구역(방)을 찾았다는 것이므로

방의 수를 나타내는 room_cnt를 증가시킨다

 

max_size

구역(방) 크기의 최대값을 저장해 놓은 변수

방을 발견했을 때마다 max를 통해 해당 값을 update 해준다

 

integrated_max

합쳐진 방의 최대 크기를 저장해놓는 변수

3번을 구할 때, 각각의 조건이 만족되면 max를 통해 해당 값을 update한다

 

 

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



# # M x N이므로
# N, M 이 주어지고 
# 이진수의 각 비트로 주어짐 = 0001 - 서 / 0010 - 북 / 0100 - 동 / 1000 - 남

from collections import deque

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

class space:
    west = False
    north = False
    east = False
    south = False

    def set_dir(self, west, north, east, south):
        self.west = west
        self.north = north
        self.east = east
        self.south = south


castle = [[space() for j in range(N)] for i in range(M)]
visited_total = [[0] * N for i in range(M)]

def set_space_dir(idx, flag, space):
    if idx == 0 and flag == '1':
        space.south = True

    if idx == 1 and flag == '1':
        space.east = True

    if idx == 2 and flag == '1':
        space.north = True

    if idx == 3 and flag == '1':
        space.west = True


for i in range(M):
    input_data = list(map(int, input().split()))
    for j in range(N):
        if i == 0: 
            castle[i][j].north = True

        if i == M-1:
            castle[i][j].south = True

        if j == 0:
            castle[i][j].west = True
        
        if j == N-1:
            castle[i][j].east = True

        num_bin = format(input_data[j],'b').zfill(4)
        for idx in range(4):
            set_space_dir(idx, num_bin[idx], castle[i][j])


# 방의 개수 room_cnt 
# 방의 크기를 구하기 위해서는 bfs

room_cnt = 0
max_size = 0
integrated_max_size = 0
for i in range(M):
    for j in range(N):
        q = deque()
        room_visitied = [[False]* N for i in range(M)]

        if visited_total[i][j] != 0:
            continue
        size = 0
        q.append((i, j))
        size +=1
        room_cnt += 1
        room_visitied[i][j] = True
        
        while q:
            row, col = q.popleft()

            if castle[row][col].north is False and room_visitied[row-1][col] is False:
                q.append((row-1, col))
                room_visitied[row-1][col] = True
                size +=1
            
            if castle[row][col].south is False and room_visitied[row+1][col] is False:
                q.append((row+1, col))
                room_visitied[row+1][col] = True
                size +=1
            
            if castle[row][col].west is False and room_visitied[row][col-1] is False:
                q.append((row, col-1))
                room_visitied[row][col-1] = True
                size +=1
            
            if castle[row][col].east is False and room_visitied[row][col+1] is False:
                q.append((row, col+1))
                room_visitied[row][col+1] = True
                size +=1

        if max_size < size:
            max_size = size

        for ni in range(M):
            for nj in range(N):
                if room_visitied[ni][nj] is True:
                    visited_total[ni][nj] = size
                    
                    if castle[ni][nj].north is True and ni-1 >= 0 and visited_total[ni-1][nj] != 0 and room_visitied[ni-1][nj] is False:
                        integrated_max_size = max(integrated_max_size, size + visited_total[ni-1][nj])

                    if castle[ni][nj].west is True and nj-1 >= 0 and visited_total[ni][nj-1] != 0 and room_visitied[ni][nj-1] is False:
                        integrated_max_size = max(integrated_max_size, size + visited_total[ni][nj-1])

                    if castle[ni][nj].south is True and ni+1 < M and visited_total[ni+1][nj] != 0 and room_visitied[ni+1][nj] is False:
                        integrated_max_size = max(integrated_max_size, size + visited_total[ni+1][nj])

                    if castle[ni][nj].east is True and nj+1 < N and visited_total[ni][nj+1] != 0 and room_visitied[ni][nj+1] is False:
                        integrated_max_size = max(integrated_max_size, size + visited_total[ni][nj+1])

                    


print(room_cnt)
print(max_size)
if M==1 and N == 1:
    print(visited_total[0][0])
else:
    print(integrated_max_size)

 

코드 개선하기

백준 강의를 듣고 코드를 게선하였다

 

개선1 

현재 내가 진행했던 방법은 visited에 해당 방(구역)의 size를 저장해놓는 방법이었는데

room 배열은 따로 두고 해당 배열에 각 room idx에 따라 size를 넣는다

visited 에는 해당 방(구역)의 room idx를 저장

 

개선2

2진법 string으로 변환하고 해당 값으로 보는 것보다 

left shift와 비트 and를 사용 -> 0보다 큰 값이 나오는 경우 : 벽이 있다 / 0이 나오는 경우 : 벽이 없다

 

개선3

합칠 방을 계산할 때, visited에 이미 해당 room_idx를 넣어놓았으므로

각 칸을 다니면서 인접하는 칸이 다른 room_idx를 가지고 있으면 합쳐보고 max 처리한다

 

from collections import deque

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

visited = [[0]*N for _ in range(M)]
room_size = [0]# room 은 idx 1부터 들어감

# 서쪽 1, 북쪽 2, 동쪽 4, 남쪽 8
dx = [0, -1, 0, 1]
dy = [-1, 0, 1, 0]

def bfs(i, j, room_idx):
    q = deque()
    q.append((i, j))
    size = 0
    visited[i][j] = room_idx

    while q:
        row, col = q.popleft()
        size += 1

        for d in range(4):
            nrow = row + dx[d]
            ncol = col + dy[d]

            if nrow < 0 or nrow >=M or ncol < 0 or ncol >= N :
                continue
            
            if (wall[row][col] & (1<<d)) > 0: 
                # 해당 방향에 벽이 존재한다는 뜻
                continue

            if visited[nrow][ncol] == 0:
                q.append((nrow, ncol))
                visited[nrow][ncol] = room_idx

    return size


max_room_size = 0
room_idx = 0
for i in range(M):
    for j in range(N):
        if visited[i][j] == 0:
            room_idx += 1
            size = bfs(i, j, room_idx)
            max_room_size = max(size, max_room_size)
            room_size.append(size)

max_integrated_room = 0
for i in range(M):
    for j in range(N):
        for d in range(4):
            nx = i + dx[d]
            ny = j + dy[d]
            if nx < 0 or nx >=M or ny < 0 or ny >= N :
                continue


            if visited[i][j] != visited[nx][ny]:
                max_integrated_room = max(max_integrated_room, room_size[visited[nx][ny]] + room_size[visited[i][j]])


print(room_idx)
print(max_room_size)
print(max_integrated_room)