백준 1236번- '성 지키기' (PYTHON 풀이)

문제:

 

가로 세로 길이를 입력받고, 경비원이 어디있는지 주어질 때 모든 행과 모든 열에 한 명 이상의 경비원을 배치할 수 있도록 필요한 경비원의 최솟값을 구하는 문제이다.

필자는 처음 모든 행에만 경비원이 존재하면 된다고 문제를 잘못 봐서 왜 틀렸는지 헤멨었는데 독자분들은 이 점을 잘 유의해서 풀길 바란다. 모든 행 & 모든 열이다!

 

풀이:

import sys
input = sys.stdin.readline

a,b = map(int, input().split())

castle = []
for i in range(a):
    row = input()
    castle.append(row)

row_count = 0
for j in range(a):
    if 'X' not in castle[j]:
        row_count += 1

col_count = 0
for k in range(b):
    guard = False
    for j in range(a):
        if castle[j][k] == 'X':
            guard = True
            break
    if not guard:
        col_count += 1

if row_count > col_count:
    print(row_count)
else:
    print(col_count)

필자는 이번 문제에서 sys를 사용하였다. 입력값을 빠르게 받기 위함이기도 하고, 한 줄씩 받아야한다고 판단을 해서 readline을 썼다.

그리고 앞서 말한대로 가로, 세로의 크기를 입력받고, 리스트를 하나 선언한다. 이후 행별 입력값을 전부 castle 리스트에 추가한다. 그럼 castle = ['X....', '.....', '....X'] 대충 이런 식으로 완성이 될 것이기 때문에 for문에서 각 라인에 해당하는 값을 가지고와서 X가 없는지 확인하고 그렇다면 row_count를 1씩 증가한다. 이 과정을 거치면 행 기준 필요한 경비원의 횟수를 구할 수 있다.

 

그 다음은 이제 열을 확인하기 위해서 col_count를 0으로 선언하고 또 다시 for문을 돈다. 앞서 말한 것처럼 행을 확인하기 위해선 입력받은 값 그대로를 리스트에 넣어서 비교하면 되지만 열은 [행][열] 로 비교해서 들어가야 하기 때문에 이중 for문이 필요하다.

그 다음 guard라는 변수를 False로 선언하다. 이는 추후에 경비원이 존재했는지 아닌지를 쉽게 판단하기 위해 선언하였다.

그리고 안쪽 for문을 작성해서 [행][열] 구조로 만들었다. 이는 각 자리마다 X가 존재하면 guard가 True로 바뀌어서 반복문을 탈출하게 되고, 다음 바깥 for문을 돌기 위해 k가 1 증가하게 될 것이다. 만약, 반대로 해당 라인에 X가 존재하지 않는다면 guard가 False이므로 if문이 실행되어서 col_count가 1씩 증가하게 될 것이다.

 

이 과정을 전부 거치면 열에 대한 필요한 경비원의 수가 구해질 것이므로 둘 중 큰 값을 비교해서 출력해주면 된다.

큰 값을 출력하는 이유는 경비명 1명당 행 1개, 열 1개를 동시에 커버하기 때문에 그냥 큰 값만 출력하면 된다! 이는 예시를 들어서 실행해보면 충분히 이해될 것이다.

예를 들어, 

[ X X X

  .  .  .

  .  .  . ]  

라면 row_count는 2, col_count는 0이므로 비어있는 행 즉, 2개만 선택하면 된다. 그래서 결국 max(2,0)이므로 앞서 말한 내용과 일치한다!