[백준(BOJ)] 2234번 : 성곽 - PYTHON[파이썬]

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

2234번: 성곽

 

---

⊙ 문제

⊙ 입력

⊙ 출력

⊙ 예제 입출력

⊙ 알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색
• 비트마스킹

 

---

 

⊙ 문제 접근 과정

 

   11 & 1 = 1011 & 0001 = 0001

   11 & 2 = 1011 & 0010 = 0010

   11 & 4 = 1011 & 0100 = 0000

   11 & 8 = 1011 & 1000 = 1000

위 코드가 핵심 코드다.

 

모든 값이 0이라면 벽으로 안 막혀 있다. 따라서 비교 연산자인 &를 사용하여 필터링을 해주면 된다.

 

BFS 호출 횟수 = 이 성에 있는 방의 개수

 

BFS 속에서 count up을 해주고 그 값을 저장해주면 방의 넓이가 된다.

그 넓이끼리 비교해주면 가장 넓은 방의 넓이를 구할 수 있다.

 

3번은 코드를 새로 만들어주어서 벽이 있는 방에 대해 벽을 하나 허물어주면 값을 구할 수 있다.

 

---

 

⊙ 문제 풀이

 

from collections import deque
import sys

input = sys.stdin.readline
dx = [0, -1, 0, 1]
dy = [-1, 0, 1, 0]
N, M = map(int, input().split())
s = [list(map(int, input().split())) for i in range(M)]
visit = [[0] * N for i in range(M)]

def bfs(x,y):
    q = deque()
    q.append([x,y])
    visit[x][y]=1
    room=1
    while q:
        x, y = q.popleft()
        wall = 1
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if ((s[x][y] & wall) != wall): 
                if 0<=nx<M and 0<=ny<N and not visit[nx][ny]:
                    room+=1
                    visit[nx][ny]=1
                    q.append([nx,ny])
            wall=wall*2
    return room
    
roomCnt = 0
maxRoom = 0
delRoom = 0

for i in range(M):
    for j in range(N):
        if visit[i][j] == 0:
            roomCnt += 1
            maxRoom = max(maxRoom, bfs(i, j))

for i in range(M):
    for j in range(N):
        num = 1
        while num < 9:
            if num & s[i][j]:
                visit = [[0] * N for _ in range(M)]
                s[i][j] -= num
                delRoom = max(delRoom, bfs(i, j))
                s[i][j] += num
            num *= 2
            
print(roomCnt)
print(maxRoom)
print(delRoom)

 

---

⊙ 결과

 

---

⊙ 마무리

 

 

NONE

 

 

좋아요는 로그인하지 않아도 누를 수 있습니다!