백준 2234번 성곽 (Python 3)

Baekjoon online judge 2234번 파이썬

 

링크

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

2234번: 성곽

비트마스킹 응용문제

1. 이 성에 있는 방의 개수
2. 가장 넓은 방의 넓이

는 쉽게 구할 수 있다.

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

이 문제인데, 모든 방을 돌면서 부술 수 있는 벽인지 확인하고 부수고, bfs돌리고, 다시 벽을 원상복귀시킨다.

 

소스코드

import sys
from collections import deque
input = sys.stdin.readline
index=[[1,-1,0],[2,0,-1],[4,1,0],[8,0,1]]

m,n=map(int,input().split())

map_data=[list(map(int,input().split())) for _ in range(n)]

def bfs(sx,sy):
  global visited
  queue=deque()

  queue.append([sx,sy])
  visited[sy][sx]=True
  cnt=1
  while queue:
    x,y=queue.popleft()

    for i,indx,indy in index:
      if not i&map_data[y][x]:
        nx=x+indx
        ny=y+indy

        if 0<=nx<m and 0<=ny<n and not visited[ny][nx]:
          visited[ny][nx]=True
          cnt+=1
          queue.append([nx,ny])

  return cnt

visited=[[False for _ in range(m)] for _ in range(n)]

now_max=-1
room_cnt=0

for i in range(n):
  for j in range(m):
    if not visited[i][j]:
      temp=bfs(j,i)
      now_max=max(now_max,temp)
      room_cnt+=1

print(room_cnt)
print(now_max)
wall=[1,2,4,8]
now_max=-1
for i in range(n):
  for j in range(m):
    for w in wall:
      if w&map_data[i][j]:
        visited = [[False for _ in range(m)] for _ in range(n)]
        map_data[i][j]-=w
        now_max=max(now_max,bfs(j,i))
        map_data[i][j]+=w
print(now_max)