백준#1236 성 지키기
문제
https://www.acmicpc.net/problem/1236
나의 풀이
- 시간초과
R, C = [int(x) for x in input().split()]
castle = []
for _ in range(R):
castle.append([x for x in input()])
# print(castle)
unsafe_rows = set([x for x in range(R)])
unsafe_columns = set([x for x in range(C)])
rlt = 0
while len(unsafe_columns) > 0 or len(unsafe_rows) > 0:
# print(unsafe_columns, unsafe_rows)
for (row_index, row) in enumerate(castle):
if 'X' in row:
if row_index in unsafe_rows:
if row_index in unsafe_rows:
unsafe_rows.remove(row_index)
for (col_index, col) in enumerate(row):
if 'X' in col:
if col_index in unsafe_columns:
unsafe_columns.remove(col_index)
# else:
# if unsafe_columns:
# unsafe_columns.remove(list(unsafe_columns)[0])
# if row_index in unsafe_rows:
# unsafe_rows.remove(row_index)
# rlt += 1
for row_index in unsafe_rows:
cols = list(unsafe_columns)
if cols:
unsafe_columns.remove(cols[0])
rlt += 1
# if unsafe_rows:
# rlt += len(list(unsafe_rows))
# unsafe_rows = set({})
print(rlt)
- 맞은 풀이
R, C = [int(x) for x in input().split()]
castle = []
for _ in range(R):
castle.append([x for x in input()])
# print(castle)
unsafe_rows = set([x for x in range(R)])
unsafe_columns = set([x for x in range(C)])
rlt = 0
while len(unsafe_columns) > 0 or len(unsafe_rows) > 0:
# print(unsafe_columns, unsafe_rows)
for (row_index, row) in enumerate(castle):
if 'X' in row:
if row_index in unsafe_rows:
if row_index in unsafe_rows:
unsafe_rows.remove(row_index)
for (col_index, col) in enumerate(row):
if 'X' in col:
if col_index in unsafe_columns:
unsafe_columns.remove(col_index)
# else:
# if unsafe_columns:
# unsafe_columns.remove(list(unsafe_columns)[0])
# if row_index in unsafe_rows:
# unsafe_rows.remove(row_index)
# rlt += 1
# print(unsafe_rows)
# del_list = []
for row_index in unsafe_rows:
cols = list(unsafe_columns)
rlt += 1
if cols:
unsafe_columns.remove(cols[0])
unsafe_rows = set()
rlt += len(list(unsafe_columns))
unsafe_columns = set()
# # for item in del_list:
# unsafe_rows = set()
# # if unsafe_rows:
# # rlt += len(list(unsafe_rows))
# # unsafe_rows = set({})
print(rlt)
남의 풀이
- 모든 행과 모든 열에 한 명 이상의 경비원이 있어야 한다
- 행기준/열 기준으로 필요한 경비원의 수를 각각 계산하여 더 큰 수를 출력한다
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))
Author And Source
이 문제에 관하여(백준#1236 성 지키기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@muchogusto/백준1236-성-지키기저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)