[백준][python]2234 성곽

문제

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

소스코드

import sys
from collections import deque
input = sys.stdin.readline
if __name__ == "__main__":
    m,n = map(int,input().split())
    room_input = [list(map(int,input().split())) for _ in range(n)]
    room_2 = [[] for _ in range(n)]
    for i in range(n):
        for j in range(m):
            changeVal = bin(room_input[i][j])[2:]
            room_2[i].append(list(map(int,'0'*(4-len(changeVal))+changeVal)))

    def bfs(X,Y):
        dx = [1,0,-1,0]
        dy = [0,1,0,-1]

        q = deque()
        q.append([X, Y])
        cnt = 1

        while q:
            x, y = q.popleft()
            for kk in range(4):
                if not room_2[x][y][kk]:
                    xx = x + dx[kk]
                    yy = y + dy[kk]
                    if 0 <= xx < n and 0 <= yy < m and not visited[xx][yy]:
                        q.append([xx, yy])
                        visited[xx][yy] = 1
                        cnt += 1
        return cnt

    visited = [[0] * m for _ in range(n)]
    res1,res2 = 0,0
    for i in range(n):
        for j in range(m):
            if not visited[i][j]:
                visited[i][j] = 1
                res1 +=1
                res2 = max(bfs(i,j),res2)

    res3 = 0
    for i in range(n):
        for j in range(m):
            for k in range(2):
                if room_2[i][j][k]:
                    room_2[i][j][k] = 0
                    visited = [[0] * m for _ in range(n)]
                    for xx in range(n):
                        for yy in range(m):
                            if not visited[xx][yy]:
                                visited[xx][yy] = 1
                                res3 = max(bfs(xx,yy),res3)
                    room_2[i][j][k] = 1

    print(res1)
    print(res2)
    print(res3)

설명

문제에 나와있는 2진수와 방향, 갈 수 있는 정보를 치환하면 아래와 같다.

8421:남동북서(아래 오른쪽 위 왼쪽), 0이면 갈 수 있음

 

1. 들어오는 숫자를 4자리 이진수로 치환해준다.

2. bfs를 이용해서 방의 갯수과와 방의 넓이를 계산해준다. (2번과 3번을 동시에 할 수 없어서 bfs를 따로 함수로 빼주었다.)

3. 백트래킹을 이용해서 벽을 하나씩 지워준다.

3-1. 벽을 지운 후 bfs를 이용해서 2번 과정을 거쳐 최대 방의 넓이를 계산해준다.

3-2. bfs를 체크할 때 인접한 부분은 탐색을 피해야하기 때문에 아래쪽과 오른쪽만 탐색해줬다. (왼쪽과 위쪽은 그 전 단계의 오른쪽과 아래쪽이기 때문이다)

 

 

 

후기

3번 과정을 보면 4중 포문을 써야한다;;; python으로는 시간초과가 나고 pypy로 통과했다. 수정할 수 있는 방법을 생각해봐야겠다.