[백준] #1236 성 지키기

 문제

 

[문제 링크]

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

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

 

 

 풀이 방법

 

[변수]

guard: 경비원 수

nec1: 각 행에 필요한 경비원 수

nec2: 각 열에 필요한 경비원 수

realnec: 실제 필요한 경비원 수

x, y: 열, 행

arr: 성의 크기 (배열)

 

[풀이]

Step1. 열과 행을 입력 받고 arr 배열에 삽입하여 성의 크기를 지정한다.

Step2. 경비원의 위치를 알 수 있는 문자열 s를 입력 받고, tocharArray를 이용하여 각 i(열)마다 y(행)크기 만큼 문자를 나눠서 경비원의 위치를 나타낸다.

Step3. 이중 반복문을 사용하여 각 행에 경비원이 있는지 확인하고 없다면 nec1을 1씩 증가시킨다.

Step4. 마찬가지로 이중 반복문을 사용하여 각 열에 경비원이 있는지 확인하고 없다면 nec2를 1씩 증가시킨다.

Step5. 열에 필요한 guard의 수와 행에 필요한 guard의 수를 비교하여 더 큰 것을 선택하여 출력한다.

 

 

[+]

String.toCharArray()

- 문자열을 한 글자씩 쪼개서 이를 char 타입의 배열에 집어 넣어주는 메소드

String s1 = "hello";
char[] charArr = s1.toCharArray();	//charArr 배열에 문자 하나씩 저장

 여기에 추가로 char형 배열을 합쳐서 다시 하나의 문자열을 만들 수 있다.

String s2 = new String(charArr);

 

 

 

 작성 코드

 

import java.util.Scanner;

public class CastleGuard {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);

        int i, j;
        int guard=0, nec1=0, nec2=0; //nec1: 행에 필요한, nec2: 열에 필요한 guard 수
        int realnec; //실제 필요한 guard
        int x= sc.nextInt(); //열
        int y= sc.nextInt(); //행
        char arr[][]= new char [x][y];

//guard 위치 배열로 저장
        for(i=0;i<x;i++) {
            String s =sc.next();
            arr[i]=s.toCharArray();
        }

//각 행에서 guard가 없다면 행에 필요한 guard 수(nec1) 증가
        for(i=0;i<x;i++) {
            for(j=0;j<y;j++) {
                if(arr[i][j]!='.') guard++;
            }
            if(guard==0) nec1++;
            guard=0;
        }

//각 열에서 guard가 없다면 열에 필요한 guard 수(nec2) 증가
        for(j=0;j<y;j++) {
            for(i=0;i<x;i++) {
                if(arr[i][j]!='.')guard++;
            }
            if(guard==0) nec2++;
            guard=0;
        }

//행에 필요한 guard 수와 열에 필요한 guard 수 비교해서 큰 것 선택
        if(nec1>nec2) realnec=nec1;
        else realnec=nec2;

        System.out.println(realnec);
    }

}