BOJ 2897 - 몬스터 트럭

문제

BOJ 2897 - 몬스터 트럭

R x C 격자에 건물(#)과 일반 차(X)가 있다. 2x2 크기의 몬스터 트럭을 주차할 수 있는 모든 위치를 확인하고, 부수는 차의 수(0~4대)별 주차 가능 횟수를 구하라. 건물이 있으면 해당 위치에는 주차 불가하다.

입력

격자 크기 R, C와 R줄의 격자 문자열이 주어진다. .은 빈 칸, X는 차, #은 건물이다.

출력

일반 차 0대~4대를 부수고 주차할 수 있는 위치의 수를 5줄에 걸쳐 출력한다.

예제

풀이

2x2 영역을 모든 가능한 위치에서 확인하여, 건물 포함 여부와 차 개수를 센다.

1. 격자의 모든 (i, j) 위치에 대해 2x2 영역 (i, j), (i, j+1), (i+1, j), (i+1, j+1)을 검사한다
2. 2x2 영역에 건물(#)이 하나라도 있으면 주차 불가 — 건너뛴다
3. 건물이 없는 경우 차(X)의 개수를 세어 해당 인덱스의 카운터를 증가시킨다
4. 차가 0대면 인덱스 1, 14대면 인덱스 cnt + 1에 기록하여 0대4대 결과를 출력한다

핵심 아이디어: 2x2 영역의 좌상단 좌표 (i, j)를 기준으로 4칸을 검사하므로, 범위는 (R-1) x (C-1)이다.

코드

dxy = [(0, 0), (0, 1), (1, 0), (1, 1)]
 
 
def search(x, y):
    cnt = 0
    for i, j in dxy:
        dx = i + x
        dy = j + y
        if 0 <= dx < r and 0 <= dy < c:
            if matrix[dx][dy] == "#":
                return 0
            elif matrix[dx][dy] == "X":
                cnt += 1
    return 1 if not cnt else cnt + 1
 
 
r, c = list(map(int, input().split()))
matrix = [list(input()) for _ in range(r)]
rst = [0] * 6
 
for i in range(r - 1):
    for j in range(c - 1):
        rst[search(i, j)] += 1
for i in range(1, len(rst)):
    print(rst[i])

복잡도

• 시간: O(R x C) — 모든 2x2 위치를 순회하며 상수(4칸) 검사
• 공간: O(R x C) — 격자 저장