문제 링크
https://www.acmicpc.net/problem/2234
🕒 Python 풀이시간: 30분
import sys
from collections import deque
dx=[0,-1,0,1]
dy=[-1,0,1,0]
input=sys.stdin.readline
N,M=map(int,input().split())
board=[]
for _ in range(M):
arr=list(map(int,input().split()))
board.append(arr)
visited=[[False]*N for _ in range(M)]
roomDict=dict()
def bfs(x,y):
global visited, largestRoomSize, roomDict, roomCnt
q=deque()
thisRoomBlocks=[]
thisRoomBlocks.append((x,y))
q.append((x,y))
visited[x][y]=True
thisRoomSize=1
while q:
now=q.popleft()
for i in range(4):
nx=now[0]+dx[i]
ny=now[1]+dy[i]
if nx<0 or ny<0 or nx>=M or ny>=N:
continue
if board[now[0]][now[1]]&(1<<i):
continue
if visited[nx][ny]:
continue
visited[nx][ny]=True
q.append((nx,ny))
thisRoomBlocks.append((nx,ny))
thisRoomSize+=1
roomDict[roomCnt]=thisRoomBlocks
largestRoomSize=max(largestRoomSize,thisRoomSize)
roomCnt=0
largestRoomSize=0
for i in range(M):
for j in range(N):
if not visited[i][j]:
bfs(i,j)
roomCnt+=1
sumOfLargestTwoRoomSize=0
for i in range(roomCnt-1):
for j in range(i+1,roomCnt):
for x1,y1 in roomDict[i]:
enabled=False
for x2,y2 in roomDict[j]:
if (abs(x1-x2)==1 and abs(y1-y2)==0) or (abs(y1-y2)==1 and abs(x1-x2)==0):
enabled=True
sumOfLargestTwoRoomSize=max(sumOfLargestTwoRoomSize,len(roomDict[i])+len(roomDict[j]))
break
if enabled:
break
print(roomCnt)
print(largestRoomSize)
print(sumOfLargestTwoRoomSize)🧱 BFS와 비트마스킹의 만남: 벽을 넘어서라!
BFS의 간단한 유형이면서 비트마스킹을 이용할줄 알면 편한 문제이다. 해당 벽의 존재 유무를 비트마스킹을 쓰라고 유도해서 제시해주기 때문이다.
기존의 BFS 자체를 그대로 사용하는 것은 별로 다를게 없다. 다만 이제 벽이 있느냐 없느냐를 두고 이동시킬 때 비트마스크의 & 연산을 이용해서 확인해주면 된다. 이 때 4자리 비트의 각 자리의 방향을 지정해서 주기에 이를 보고 방향을 dx, dy로 설정해주기만 하면 된다.
벽을 하나 없애서 만들 수 있는 가장 큰 방의 경우는 각 모든 방의 상태를 저장해놓은 다음 비교해서 구했다. 붙어있는 블록이 있다면 벽을 없애볼 수 있기에 이를 활용하였다.
이렇게 Python로 백준의 "성곽" 문제를 해결해보았습니다. 코드와 개념 설명을 참고하여 문제를 해결하는 데 도움이 되셨길 바랍니다! 😊
