백준 1236 : 성지키기 (C언어)

문제

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

1236번: 성 지키기

---

문제

영식이는 직사각형 모양의 성을 가지고 있다. 성의 1층은 몇 명의 경비원에 의해서 보호되고 있다. 영식이는 모든 행과 모든 열에 한 명 이상의 경비원이 있으면 좋겠다고 생각했다.

성의 크기와 경비원이 어디있는지 주어졌을 때, 몇 명의 경비원을 최소로 추가해야 영식이를 만족시키는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 성의 세로 크기 N과 가로 크기 M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 성의 상태가 주어진다. 성의 상태는 .은 빈칸, X는 경비원이 있는 칸이다.

출력

첫째 줄에 추가해야 하는 경비원의 최솟값을 출력한다.

예제 입력 1 복사

4 4
....
....
....
....

예제 출력 1 복사

4

예제 입력 2 복사

3 5
XX...
.XX..
...XX

예제 출력 2 복사

0

예제 입력 3 복사

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

예제 출력 3 복사

3

출처

• 문제를 번역한 사람: baekjoon

알고리즘 분류

• 구현

 

---

#include<stdio.h>
int main(void) {
    int n, m, i, j, ii=0, jj=0;
    scanf("%d %d", &n, &m);
    char castle[n][m];
    for(i = 0; i < n; i++){
        for(j = 0; j < m; j++){
            scanf("%c", &castle[i][j]);
            if(castle[i][j] == '\n')
                j--;
        }
    }
    
    for(i=0;i<n;i++){
        for(j=0;j<m;j++){
            if(castle[i][j] == 'X')
                break;
            if(j == m - 1)
                ii++;
        }
    }
    for(i=0;i<m;i++){
        for(j=0;j<n;j++){
            if(castle[j][j] == 'X')
                break;
            if(j == m-1)
                jj++;
        }
    }
    
    printf("%d", ii>=jj?ii:jj);
}

상하 좌우로 적어도 한명의 경비병은 있어야 한다고 합니다.

가로 세로 각각 몇명의 경비원이 필요한지 확인하고 더 큰 값만큼 경비병을 출력해 주시면 됩니다.

ii값에는 몇개의 가로열에 경비원이 필요한지, jj값에는 몇개의 세로열에 경비원이 필요한지 카운트 하여

마지막 줄에서 더 큰 값을 출력할 수 있도록 하였습니다.

 

---

Git Hub

BaekJoon-Study/1236 : 성지키기.c at C · GUuu9/BaekJoon-Study (github.com)

GitHub - GUuu9/BaekJoon-Study