백준#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))