백준 2234 성곽 (파이썬)

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

2234번: 성곽

1. 동서남북에 맞춰 방향과 마주칠 벽의 번호 설정. (동쪽으로 이동할 경우 다음칸의 서쪽벽과 마주침)

2. 비트연산으로 현재 이동방향과 다음칸에 벽이 있는지 확인하면서 이동

3. 필요한 답을 반복문으로 출력

from collections import deque
import sys

input = sys.stdin.readline
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]
dir = [1, 2, 4, 8]

def bfs(x, y, cnt):
    q.append([x, y])
    c[x][y] = cnt
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < m and 0 <= ny < n:
                if dir[i] & ~a[nx][ny] and c[nx][ny] == 0:
                        c[nx][ny] = cnt
                        q.append([nx, ny])

n, m = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(m)]
c = [[0]*n for _ in range(m)]
q = deque()

cnt = 1
for i in range(m):
    for j in range(n):
        if c[i][j] == 0:
            bfs(i, j, cnt)
            cnt += 1
print(cnt-1)

ans = [0]*(cnt-1)
for i in range(m):
    for j in range(n):
        ans[c[i][j]-1] += 1
print(max(ans))

max_room = 0
for i in range(m):
    for j in range(n):
        for k in range(4):
            ni = i + dx[k]
            nj = j + dy[k]
            if 0 <= ni < m and 0 <= nj < n:
                if c[i][j] != c[ni][nj]:
                    room = ans[c[i][j]-1] + ans[c[ni][nj]-1]
                    max_room = max(room, max_room)
print(max_room)