난이도

Gold 5

인증

문제

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

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

입력

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

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

출력

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

예제 입력

3 3
XXX
X.X
XXX

예제 출력

해설 및 후기

처음엔 막막했으나 의외로 제한이 널널해 풀 수 있었다. 왜냐하면 순차 탐색이 가능하기 때문이다.

그러면 각 블록들을 순회하면서, 연속된 두 블록을 찾기만 하면 된다. 총 네 방향이 가능하므로, 오른쪽으로 순회하거나 아래로 순회하면서 각 케이스를 탐색한다.

제출 코드

import sys
m,n = map(int,sys.stdin.readline().rstrip().split())
l = []
for i in range(m):
    l.append(sys.stdin.readline().rstrip())
r = 0
for i in range(m):
    utmp = 0
    dtmp = 0
    for j in range(n):
        if(i > 0):
            if(l[i-1][j] == 'X' and l[i][j] == '.'):utmp += 1
            else: 
                r += utmp // 2 
                utmp = 0
        if(i < m-1):
            if(l[i+1][j] == 'X' and l[i][j] == '.'):dtmp += 1
            else: 
                r += dtmp // 2
                dtmp = 0

for i in range(n):
    ltmp = 0
    rtmp = 0
    for j in range(m):
        if(i > 0):
            if(l[j][i-1] == 'X' and l[j][i] == '.'):ltmp += 1
            else: 
                r += ltmp // 2
                ltmp = 0
        if(i < n-1):
            if(l[j][i+1] == 'X' and l[j][i] == '.'):rtmp += 1
            else:
                r += rtmp // 2
                rtmp = 0

print(r)