[python] 백준 2234 성곽

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

2234번: 성곽

 

 

문제 해결

• 우선 숫자에 따라 벽이 존재유무를 확인할 수 있다.
• 남: 8, 동:4, 북:2, 서:1인 만큼 bfs의 이동방향도 남, 동, 북, 서 순서대로 해서 값을 비교해서 벽의 존재유무를 알 수 있다.
• 벽이 존재하지 않으면 일반 bfs와 다를바가 없다.
• 다만 각 영역에 대한 기록을 해야하므로 room_info를 통해 group_num과 땅 사이즈를 위치마다 기록을 한다.
• 하나의 벽을 허물 때 벽을 끼고 있는  땅의 group_num이 다르다는 조건이 충족한다면 두 땅을 합쳤을 때 최대 땅 사이즈를 비교해가며 벽 하나를 허물 때 가장 큰 사이즈의 땅의 크기를 구할 수 있다.

 

CODE

from collections import deque


def bfs(x,y):
    global group_num
    
    visited[x][y] = 1
    que = deque()
    que.append((x,y))
    
    area = 1
    
    group = []
    group.append((x,y))
    while que:
        px, py = que.popleft()
        wall = arr[px][py]
        for i in range(4):
            if wall>=binary[i]: # 벽이 존재
                wall -= binary[i]
            else: # 벽이 존재하지 않아 연결됨
                nx, ny = px+dx[i], py+dy[i] 
                if 0<=nx<M and 0<=ny<N and not visited[nx][ny]:
                    area += 1
                    que.append((nx,ny))
                    visited[nx][ny] = 1
                    group.append((nx,ny))
    for i,j in group:
        room_info[i][j].append(group_num)
        room_info[i][j].append(area)
    group_num += 1
    return area


if __name__=='__main__':
    N, M = map(int, input().split())
    arr = [list(map(int, input().split())) for _ in range(M)]
    binary = [8, 4, 2, 1]
    
    dx = [1, 0, -1 ,0]
    dy = [0, 1, 0, -1]
    
    cnt = 0
    visited = [[0 for _ in range(N)] for _ in range(M)]
    room_info = [[[] for _ in range(N)] for _ in range(M)] # 속한 그룹 땅 넘버, 크기를 저장
    
    group_num = 0
    max_area = 0
    for i in range(M):
        for j in range(N):
            if not visited[i][j]:
                max_area = max(bfs(i,j), max_area)
                cnt += 1
    
    maybe_max = 0
    for i in range(M):
        for j in range(N):
            for d in range(4):
                if arr[i][j] >= binary[d]:
                    nx, ny = i+dx[d], j+dy[d]
                    if 0<=nx<M and 0<=ny<N:
                        if room_info[i][j][0] != room_info[nx][ny][0]:
                            maybe_max = max(maybe_max, room_info[i][j][1] + room_info[nx][ny][1])
    print(cnt)
    print(max_area)
    print(maybe_max)