Problem Solving/Online Judge
[BOJ] #1236 - 성 지키기
se0m
2021. 6. 15. 17:59
1236번: 성 지키기
첫째 줄에 성의 세로 크기 N과 가로 크기 M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 성의 상태가 주어진다. 성의 상태는 .은 빈칸, X는 경비원이 있는 칸이다
www.acmicpc.net
** 문제 유형
- 순차 탐색
** 풀이
- 모든 행과 열에 한명 이상의 경비원이 있어야 함
- 행 기준/열 기준으로 필요한 경비원의 수를 계산하여 더 큰 수를 출력
# 방법 1
n, m = map(int, input().split())
array = []
for _ in range(n):
array.append(input())
row = [0] * n
column = [0] * m
for i in range(n):
for j in range(m):
if array[i][j] == 'X': # 경비원이 존재하는 위치 기록
row[i] = 1
column[j] = 1
row_count = 0
for i in range(n): # 행 기준
if row[i] == 0: # 경비원이 존재하지 않으면
row_count += 1
column_count = 0
for j in range(m): # 열 기준
if column[j] == 0: # 경비원이 존재하지 않으면
column_count += 1
print(max(row_count, column_count))
# 방법 2
n, m = map(int, input().split())
array = []
for _ in range(n):
array.append(input())
row = set()
column = set()
for i in range(n):
for j in range(m):
if array[i][j] == 'X':
row.add(i)
column.add(j)
row_count = n - len(row)
column_count = m - len(column)
print(max(row_count, column_count))