[백준 1236번] 성 지키기 (Python/파이썬)

https://www.acmicpc.net/problem/1236

1236번: 성 지키기

최근 백준 open Contest에서 그리디 + 구현 문제를 만났는데 아이디어는 바로 생각했으나 구현을 못해서 못풀었다.

구현력을 늘리고자 이 문제를 풀었다.

 

각 행과 열에는 최소 하나 이상의 경비병이 있어야한다. 최소로 경비병을 세우려면 몇명을 더 추가로 배치해야하냐는 문제이다.

필자는 2차원 배열을 받은 후에 전치행렬(행과 열을 바꾼 행렬)을 만들어서 문제를 해결하였다.

처음 원래 행렬을 스캔하다가 X가 없는 행이 나오면 그 행의 세로줄(열)을 탐색해서 탐색결과 X가 없으면 경비병을 추가하였고, X가 모두 있으면 어느 곳에다가 놔둬도 상관 없기때문에 배치는 안하고 경비병 숫자만 1 증가했다.

처음 제출했을때 틀렸는데 가로를 스캔해서 세로를 찾는 경우만 생각해서 틀렸다.

그래서 과정을 함수로 만들어 인자로 M,N, 원래 행렬, 전치행렬을 넣어서 세로를 스캔해서 가로를 찾는 경우로 해주었다.

코드는 다음과 같다.

 

import sys
input = sys.stdin.readline
N, M = map(int,input().split())
castle = []
for _ in range(N):
  castle.append(list(input().rstrip()))
num = 0

trans_castle = []
for col in range(M):
  tmp = []
  for row in castle:
    tmp.append(row[col])
  trans_castle.append(tmp)

def cnt(N,M,castle,trans_castle):
  global num
  for i in range(N):
    if 'X' not in castle[i]:
      for j in range(M):
        if 'X' not in trans_castle[j]:
          castle[i][j] = 'X'
          trans_castle[j][i] = 'X'
          num += 1
          break
      else:
        num += 1

cnt(N,M,castle,trans_castle)
cnt(M,N,trans_castle,castle)
print(num)

 

 

 

 

브론즈1짜리 문제이지만 구현력이 없어서 그런지 30분정도는 걸렸다.

대부분의 다른 사람들 풀이를 보면 행과 열만을 탐색해서 X가 없으면 카운트 하고 행과 열중에서 카운트가 더 큰것을 출력하는 방식으로 문제를 해결했다.

어쩐지 브론즈1인데 구현이 어렵더라...아쉽지만 전치행렬을 만들고, 세로축 탐색을 처음 해봤다는 것에 의미를 둬야겠다.