[Python] 1236번 성 지키기

1236번: 성 지키기 (acmicpc.net)

1236번: 성 지키기

---

 

22/09/08

 

 

그룹 채점 현황에서 무작위로 골라서 푼 문제로, 의외로 브론즈 문제 치고는 재미있는 아이디어를 가진 문제 같아서 흥미로웠다.

---

 

문제 접근 방식:

 

 

'X'표시가 되어있는 곳은 이미 경비원이 지키고 있는 줄이라는 뜻이다.

 

나는 성의 모습을 입력받고, 각 줄에 경비원이 있는지 확인하는 row_check, col_check 리스트를 1로 초기화하며 선언해주었다.

 

성의 모습을 확인하며, 만약 경비원이 지키고 있는 줄이라면 0으로 바꿔준다.

 

이후 sum(row_check)를 해주는데, 이는 경비원이 지키고 있지 않는 가로줄의 개수를 의미한다.

 

마찬가지 방법으로 세로줄도 똑같이 해주고, 경비원이 지키고 있지 않는 세로줄의 개수를 구한다.

 

이 두 개수 중 더 큰 값을 구하면 그것이 답이 되는데, 그 이유는 경비원이 지키고 있지 않은 세로줄과 경비원이 지키고 있지 않은 가로줄이 겹치는 좌표에다 경비원들을 놓으면 둘 중 작은 쪽은 해결이 되기 때문이다.

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 1236번 성 지키기
# 구현
N, M = map(int, input().split())
graph = [list(input()) for _ in range(N)]
row_check = [1 for _ in range(N)]
col_check = [1 for _ in range(M)]
for row in range(N):
    if 'X' in graph[row]:
        row_check[row] = 0
for col in range(M):
    k = [graph[row][col] for row in range(N)]
    if 'X' in k:
        col_check[col] = 0
print(max(sum(row_check),sum(col_check)))