[Python/파이썬] 백준 2115번 갤러리

2115번: 갤러리

 

문제

갤러리의 지도는 M*N의 정사각형 격자로 표현될 수 있다. 어떤 정사각형들은 벽으로 구성되어 있고, 다른 정사각형들은 빈 공간으로 구성되어 있다. 벽을 회색, 빈 공간을 흰색으로 표현하면 다음 그림과 같다.

갤러리에 그림을 걸려고 한다. 그림의 길이는 정사각형의 변의 길이의 두 배이다. 반드시 빈 공간과 인접해 있는 벽에만 그림을 걸 수 있으며, 그림들은 서로 겹칠 수 없다. 갤러리의 맵이 주어졌을 때, 최대로 걸 수 있는 그림의 개수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 갤러리의 세로 길이 M과 가로 길이 N이 주어진다. (1 ≤ M, N ≤ 1,000) 다음 M개의 줄에는 각각 N개의 문자가 주어진다. 문자는 'X' 또는 '.'이며 'X'는 벽을, '.'는 빈 공간을 나타낸다.

입력되는 모든 데이터에서 적어도 첫 줄과 마지막 줄, 첫 열과 마지막 열은 모두 벽이다.

출력

최대 그림 개수를 출력한다.

코드

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

visited = [[[False] * 4 for _ in range(n)] for _ in range(m)]
cnt = 0
for i in range(1, m-1):
    for j in range(1, n-1):
        for d in [1, -1]:
            # 가로 그림
            if map_data[i][j] == '.' and map_data[i][j+1] == '.':
                if map_data[i+d][j] == 'X' and map_data[i+d][j+1] == 'X' and not visited[i][j][d+1]:
                    visited[i][j][d+1] = True
                    visited[i][j+1][d+1] = True
                    cnt += 1    
            # 세로 그림
            if map_data[i][j] == '.' and map_data[i+1][j] == '.': 
                if map_data[i][j+d] == 'X' and map_data[i+1][j+d] == 'X' and not visited[i][j][d+2]:
                    visited[i][j][d+2] = True
                    visited[i+1][j][d+2] = True
                    cnt += 1
print(cnt)

그림들이 서로 겹치면 안되므로 visited 3차원 배열에 그림이 걸린 위치는 True로 표시해준다.

visited[i][j][k]는 갤러리 지도(map_data)의 i행 j열 k번째 벽면을 의미한다. 벽면의 순서는 아래와 같다.