[백준] 1236번 : 성 지키기

유형 : 탐색

 

[예제]

5 8
....XXXX
........
XX.X.XX.
........
........

[출력]

3

---

 

1. 내 풀이

우선 예시를 통해 문제를 이해해보자. (아래그림 참고)

 

import sys

N, M = map(int,sys.stdin.readline().split())
_list = []

result1 = 0
for i in range(N):
    tmp = sys.stdin.readline().strip()
    _list.append(tmp)
    
    if 'X' not in tmp:
        result1 += 1

result2 = 0
for i in range(M):
    cnt2 = 0
    for j in range(N):
        if _list[j][i] == 'X':
            break
        else:
            cnt2 += 1

    if cnt2 == N:
        result2 += 1

print(max(result1,result2))

▷ result1 : 행 기준, result2 : 열 기준 경비가 필요한 개수

▷ result1과 result2는 각각 기준에서 필요한 최소 개수이므로, 두 조건을 만족시키기 위해 둘 중 큰 값을 출력하면 된다.

 

 

2. 다른 풀이

출처 : 패스트캠퍼스 - 알고리즘 / 기술면접 완전 정복 올인원 패키지 Online

 

** 핵심 아이디어
1. 모든 행과 모든 열에 한 명 이상의 경비원이 있어야 한다.
2. 행 기준, 열 기준으로 필요한 경비원의 수를 각각 계산하여 더 큰 수를 출력한다.

 

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

 

 

문제 출처 : https://www.acmicpc.net/problem/1236

1236번: 성 지키기