알고리즘 - Python / 백준 - 2115번 : 갤러리

2115번: 갤러리 (acmicpc.net)

2115번: 갤러리

 

---

풀이

• 갤러리 벽에 2칸 길이의 그림을 얼마나 걸 수 있는지 최댓값을 구하는 문제이다.
• 빈공간일때 , 아래와 오른쪽을 확인하고 빈공간인지 확인한다.
• 만약 아래나 오른쪽이 빈공간이면 이전에 그 부분에 그림을 붙였는지 확인하는 check 배열을 통해 그림이 안붙어져 있다면 , 그곳에 그림을 붙인다.
• 위와 같은 방식으로 전 구간을 순회해 붙일 수 있는 그림의 최댓값을 구하면 된다.

 

import sys
n,m = map(int,sys.stdin.readline().split(" "))
stack = []
for _ in range(n):
    stack.append(list(input()))
hap = 0
check_point_ru = [ [ 0 for _ in range(m)] for _ in range(n)]
check_point_rd = [ [ 0 for _ in range(m)] for _ in range(n)]
check_point_ur = [ [ 0 for _ in range(m)] for _ in range(n)]
check_point_ul = [ [ 0 for _ in range(m)] for _ in range(n)]

def check(y,x):
    global stack
    global hap
    if stack[y][x] == ".":
        if stack[y+1][x] == ".":
            if stack[y][x-1] == "X" and stack[y+1][x-1] == "X" and check_point_ul[y][x] == 0:
                check_point_ul[y][x] = 1
                check_point_ul[y+1][x] = 1
                hap += 1
            if stack[y][x+1] == "X" and stack[y+1][x+1] == "X" and check_point_ur[y][x] == 0:
                check_point_ur[y][x] = 1
                check_point_ur[y+1][x] = 1
                hap += 1
        if stack[y][x+1] == ".":
            if stack[y-1][x] == "X" and stack[y-1][x+1] == "X" and check_point_ru[y][x] == 0:
                check_point_ru[y][x] = 1
                check_point_ru[y][x+1] = 1
                hap += 1
            if stack[y+1][x] == "X" and stack[y+1][x+1] == "X" and check_point_rd[y][x] ==0:
                check_point_rd[y][x] = 1
                check_point_rd[y][x+1] = 1
                hap += 1

for i in range(1,n-1):
    for t in range(1,m-1):
        check(i,t)
print(hap)

 

비슷한 문제

 

알고리즘 - Python / 백준 - 14397번 : 해변 (tistory.com)

알고리즘 - Python / 백준 - 14397번 : 해변

 

---