[백준/2234/파이썬] 성곽

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

2234번: 성곽

Problem

• 대략 위의 그림과 같이 생긴 성곽이 있다. 굵은 선은 벽을 나타내고, 점선은 벽이 없어서 지나다닐 수 있는 통로를 나타낸다. 이러한 형태의 성의 지도를 입력받아서 다음을 계산하는 프로그램을 작성하시오.

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

조건

• 위의 예에서는 방은 5개고, 가장 큰 방은 9개의 칸으로 이루어져 있으며, 위의 그림에서 화살표가 가리키는 벽을 제거하면 16인 크기의 방을 얻을 수 있다.
• 성은 M × N(1 ≤ M, N ≤ 50)개의 정사각형 칸으로 이루어진다. 성에는 최소 두 개의 방이 있어서, 항상 하나의 벽을 제거하여 두 방을 합치는 경우가 있다
• 첫째 줄에 두 정수 N, M이 주어진다. 다음 M개의 줄에는 N개의 정수로 벽에 대한 정보가 주어진다. 벽에 대한 정보는 한 정수로 주어지는데, 서쪽에 벽이 있을 때는 1을, 북쪽에 벽이 있을 때는 2를, 동쪽에 벽이 있을 때는 4를, 남쪽에 벽이 있을 때는 8을 더한 값이 주어진다. 참고로 이진수의 각 비트를 생각하면 쉽다. 따라서 이 값은 0부터 15까지의 범위 안에 있다.

SOL

BFS 탐색의 조건을 조금 꼬아놓은 문제이다. 벽의 위치가 직관적이지 않고, 비트로 처리해서 표기해놓은 형태이다.

 

1번 출력값은 , 연결요소의 갯수

2번 출력값은 연결요소 중, 가장 큰 연결 요소 

3번 출력값은, 연결 요소 중, 서로 연결 했을 때 가장 큰 값을 가지는 방의 크기를 출력해주면 된다.

 

연결요소를 가장 쉽게 구분해주는 방법은, 넘버링을 해주는거다. 이렇게하면, 구분할 수 있고, 연결요소의 갯수를 구할 수 있게 된다. 그리고, visited를 탐색하면서, 가장 큰 연결요소도 구할 수 있게 된다.

 

#성곽
import sys
from collections import deque
input =sys.stdin.readline

M,N =map(int,input().split())
board=[list(map(int,input().split())) for _ in range(N)]
visited=[[0]*M for _ in range(N)]
#print(board)
#print(visited)
# 동,남,서,북
dy=[0,1,0,-1]
dx=[1,0,-1,0]
# 서,북,동,남
dir=[1,2,4,8]


def bfs(y,x,cnt):
    dq=deque()
    dq.append((y,x))
    visited[y][x] = cnt
    while dq:
        y,x=dq.popleft()
        for k in range(4):
            ny=y+dy[k]
            nx=x+dx[k]
            if not (0<=ny<N and 0<=nx<M):
                continue
            # ~borad[ny][nx] 하면, 뚫려있는 곳을 알 수 있음.
            #print("ny:{},nx:{},dir:{},board:{}".format(ny,nx,dir[k],board[ny][nx]))
            #print("~board[ny][nx]:{}".format(dir[k] & ~board[ny][nx]))
            if dir[k] & ~board[ny][nx] and visited[ny][nx] ==0:
                visited[ny][nx]=cnt
                dq.append((ny,nx))
# 연결 요소 찾기 + 넘버링하기
cnt=1
for i in range(N):
    for j in range(M):
        if visited[i][j]==0:
            bfs(i,j,cnt)
            cnt+=1
#print(visited)
print(cnt-1)
# 넘버링 된 방들의 면적 구하기, 그 중 가장 넓은 방 출력
area=[0]*(cnt-1)
for i in range(N):
    for j in range(M):
        area[visited[i][j]-1]+=1
print(max(area))
# 넘버링된 방들을 가지고, 다른 방과 연결했을 때, 가장 큰 면적을 가진 연결된 방 구하기.
# 모든 지점에서 시뮬레이션을 해본다.
sweet_room=0
for i in range(N):
    for j in range(M):
        for k in range(4):
            ny=i+dy[k]
            nx=j+dx[k]
            if not (0<=ny<N and 0<=nx<M):
                continue
            # 범위 안이고 ,다른 방일 때 , 방을 합쳐본다.
            if visited[ny][nx] !=visited[i][j]:
                room=area[visited[ny][nx]-1]+area[visited[i][j]-1]
                sweet_room=max(room,sweet_room)

print(sweet_room)