[BOJ] 누울 자리를 찾아라 - 1652 (S5)

시간 제한	메모리 제한
2 초	128 MB

문제

일정한 간격으로 벽이 설치되어 있는 방이 있다. 이 방의 크기는 N×N이며 일부 칸에는 사람들이 이미 누워있다.

방은 다음과 같이 주어진다.

• .는 아무도 없는 빈 칸
• X는 누워있는 사람 또는 벽

이때, 연속해서 2칸 이상의 빈 칸이 있으면 그 곳에 누울 수 있다. 가로로 누울 수 있는 자리와 세로로 누울 수 있는 자리의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 방의 크기 N이 주어진다. (1 ≤ N ≤ 100)

둘째 줄부터 N개의 줄에 방의 정보가 주어진다. 방의 정보는 .와 X로만 이루어져 있다.

출력

첫째 줄에 가로로 누울 수 있는 자리의 개수와 세로로 누울 수 있는 자리의 개수를 공백으로 구분하여 출력한다.

풀이

이 문제는 2차원 배열에서 연속된 빈 공간을 세는 문제이다.

접근 방법

핵심 아이디어

1. 각 행을 순회하며 연속된 .의 개수를 센다
2. 연속된 빈 칸이 2개 이상이면 가로로 누울 자리 1개로 카운트
3. 세로는 배열을 transpose(전치)하여 같은 방법 적용

누울 자리 판별

• 연속된 .을 세다가 X를 만나면:
  • 지금까지 센 개수가 2 이상이면 누울 자리 1개
  • 카운터 초기화
• 행의 끝에 도달했을 때도 확인 필요

코드

def get_area_cnt(room, N):
    row_cnt = 0

    for y in range(N):
        cnt = 0
        for x in range(N):
            # print(room[y][x], end=" ")
            if room[y][x] == "X":
                if cnt >= 2:
                    row_cnt += 1
                cnt = 0
                continue
            cnt += 1
        if cnt >= 2:
            row_cnt += 1
    return row_cnt


def main():
    N = int(input())

    room = [input() for _ in range(N)]
    print(get_area_cnt(room, N), end=" ")

    room = list(zip(*room))
    print(get_area_cnt(room, N))


if __name__ == "__main__":
    main()

코드 설명

get_area_cnt 함수

def get_area_cnt(room, N):
    row_cnt = 0

    for y in range(N):
        cnt = 0
        for x in range(N):
            if room[y][x] == "X":
                if cnt >= 2:
                    row_cnt += 1
                cnt = 0
                continue
            cnt += 1
        if cnt >= 2:
            row_cnt += 1
    return row_cnt

• 각 행을 순회하며 연속된 빈 칸을 센다
• X를 만나면:
  • 지금까지 센 개수가 2 이상이면 누울 자리로 카운트
  • 카운터 초기화
• 행의 끝에서도 카운터 확인 (마지막이 빈 칸인 경우)

메인 로직

room = [input() for _ in range(N)]
print(get_area_cnt(room, N), end=" ")

room = list(zip(*room))
print(get_area_cnt(room, N))

가로 누울 자리:

• 원본 방 정보로 바로 계산

세로 누울 자리:

• zip(*room)으로 배열을 전치(transpose)
• 전치된 배열에서 같은 함수 적용

배열 전치 이해하기

room = ['..X',
        '.X.',
        'X..']

# zip(*room) 결과
transposed = [('.', '.', 'X'),  # 첫 번째 열
              ('.', 'X', '.'),  # 두 번째 열
              ('X', '.', '.')]  # 세 번째 열

전치를 하면 열이 행으로 바뀌므로, 세로 방향 확인을 가로 방향 확인과 동일한 로직으로 처리할 수 있다.

시간 복잡도

• 가로 검사: O(N²)
• 세로 검사 (전치 + 검사): O(N²)
• 전체: O(N²)

N ≤ 100이므로 최대 10,000번의 연산으로 충분히 빠르다.

예제 분석

N = 5
방:
....X
....X
.XX..
.XX..
X....

가로 누울 자리:

• 1행: .... (4칸) → 1개
• 2행: .... (4칸) → 1개
• 3행: . (1칸), .. (2칸) → 1개
• 4행: . (1칸), .. (2칸) → 1개
• 5행: .... (4칸) → 1개
• 합계: 5개

세로 누울 자리:

• 1열: ..... (5칸, X 제외하면 4칸) → …
• 전치 후 각 행 검사로 계산

주의 사항

1. 연속 2칸 이상: 정확히 2칸이 아니라 2칸 이상
2. 행의 끝 처리: 마지막 칸이 빈 칸이면 행이 끝났을 때도 카운트 확인
3. 전치 활용: 세로 검사를 위해 배열 전치 사용
4. 출력 형식: 가로와 세로를 공백으로 구분

다른 접근 방법

정규표현식을 사용할 수도 있다:

import re

N = int(input())
room = [input() for _ in range(N)]

# 가로
row_cnt = sum(len(re.findall(r'\.{2,}', row)) for row in room)

# 세로
transposed = [''.join(row[i] for row in room) for i in range(N)]
col_cnt = sum(len(re.findall(r'\.{2,}', col)) for col in transposed)

print(row_cnt, col_cnt)

정규표현식 \.{2,}는 “연속된 2개 이상의 .“을 의미한다.