[BOJ] 1236 성 지키기

문제

fail log

me

# import sys
# input=sys.stdin.readline
#
# ####
#
# n,m=map(int,input().split())
#
# castle=[list(input().strip()) for _ in range(n)]
# for c in castle:print(c)
# def checkCol(row,col,current_castle):
#     print(row,col)
#     for c in [current_castle[i][col] for i in range(n)]:
#         print(c)
#         if c=='X': return False
#     print("#####")
#     return True
#
# def dfs(depth,cnt,current_castle):
#     global min_security
#     if depth==n:
#         print("----Another end-----")
#         print(cnt)
#         for c in current_castle:print(c)
#         min_security=min(cnt,min_security)
#         return
#     else:
#         if current_castle[depth].count('X')!=0:
#             # 같은 행에 경비원 있음
#             dfs(depth+1,cnt,current_castle)
#         else:
#             for i in range(m):
#                 # if checkCol(depth,i,current_castle):
#                 current_castle[depth][i]='X'
#                 dfs(depth+1,cnt+1,current_castle)
#                 current_castle[depth][i]='.'
# min_security=int(1e9)
# dfs(0,0,castle)
# print(min_security)

import sys
input=sys.stdin.readline

####

n,m=map(int,input().split())

castle=[list(input().strip()) for _ in range(n)]
def check(depth,col,current_castle):
    for c in current_castle:print(c)
    print('*',depth,col,[current_castle[i][col] for i in range(n)])
    if current_castle[depth].count('X')==0 or [current_castle[i][col] for i in range(n)].count('X')==0:
        return True
    return False
def dfs(depth,cnt,current_castle):
    global min_security
    if depth==n:
        print('end of the line')
        for c in current_castle:print(c)
        min_security=min(cnt,min_security)
        return
    else:
        # if current_castle[depth].count('X')!=0:
        #     # 같은 행에 경비원 있음
        #     dfs(depth+1,cnt,current_castle)
        # else:
        for i in range(m):
            if check(depth,i,current_castle):
                current_castle[depth][i]='X'
                dfs(depth+1,cnt+1,current_castle)
                current_castle[depth][i]='.'
            else:
                dfs(depth+1,cnt,current_castle)
min_security=int(1e9)
dfs(0,0,castle)
print(min_security)

solution

# 모든 행과 열에 한 명 이상의 경비원이 있어야 함
# 행 기준, 열 기준으로 필요한 경비원의 수를 각각 계산하여 더 큰 수 출력
# 행 기준으로 몇 개의 행이 경비원이 없는지
# 열 기준으로 몇 개의 열이 경비원이 없는지

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))