[삼성 SDS 알고리즘 사전테스트] 마지막 생존자

[삼성 SDS 알고리즘] 마지막 생존자

지난 일요일 사전테스트가 종료되었습니다. 테스트기간동안 푼 문제 해결방법을 포스팅하려고 합니다.

문제 출처 : https://koitp.org/problem/SDS_TEST_PAGE/read/

문제

B.C 1500년경 당신은 고대 바빌로니아 왕국의 마지막 생존자들을 이끌고 북쪽으로 이동해 불모지를 지나 미개척지 땅에 들어섰습니다. 당신은 생존자들과 정찰을 통해 주변 N * N 정사각형 구역에 대해 격자 단위의 정보를 얻었습니다. 당신은 이 구역에서 도시를 세우기 적합한 지역을 찾아 그 곳에서 생존자들과 새로운 문명을 세우고자 합니다. ‘도시를 세우기 적합한 장소’ 란 도시를 세우는 위치 및 가로, 세로, 대각선의 8방향으로 인접한 위치에 불모지가 존재하지 않고, 물과 산과 초원이 모두 존재하는 지역입니다.

[그림 1]

[그림 2]

노랑색을 초원, 진녹색을 산, 파랑색을 물, 빨강색을 불모지라고 할 때, [그림 1]의 경우는 도시를 세우고자 하는 장소 및 그 주변에 불모지가 없고 물과 산과 초원이 모두 존재하므로 도시를 세우기 적합한 장소입니다. [그림 2]의 경우는 주변에 불모지가 존재하고 물이 존재하지 않기 때문에 도시를 세우기 적합한 장소가 아닙니다. 당신의 새로운 문명을 위해 도시를 세우기 적합한 장소의 개수를 출력하는 프로그램을 작성하시오.

[제한 조건]

1. N은 10 이하의 자연수이다.
2. 지도의 정보에서 불모지는 0, 물은 1, 산은 2, 초원은 3로 표현된다.
3. 지도 바깥 구역은 고려하지 않는다.
4. 수도를 건설하는 위치에 있는 정보도 도시를 세우기 적합한 장소를 계산할 때 포함된다. 즉 불모지 위에 도시를 건설할 수 없다. 단 물 위에는 도시를 건설하는 것이 가능하다.

입력

맨 처음에 테스트 케이스의 개수 T(<=20)가 주어지며 그 다음 줄부터 T개의 테스트 케이스가 주어진다. 테스트 케이스 첫 줄에는 지도의 크기 N (3 ≤ N ≤ 10)이 입력으로 주어진다. 각 테스트케이스의 두 번째 줄부터 N+1번째 줄 까지는 지도의 정보가 입력으로 주어진다. 지도의 정보는 0, 1, 2, 3의 숫자로만 구성되어 있다.

출력

각각의 테스트 케이스에 대하여 #x (x는 테스트 케이스 번호, 1부터 시작)를 출력하고 공백을 하나 둔 다음 도시를 세우기 적합한 장소의 개수를 출력하라.

힌트

(입력)
2
5
0 1 1 2 1
3 2 1 3 2
2 1 3 1 0
0 1 2 2 3 
0 0 1 1 1
5
1 1 1 1 1
2 2 2 2 2
3 3 3 3 3
2 2 2 2 2
1 1 1 1 1

(출력)
#1 7
#2 10

계획 및 분석

조건에 대해 잘 이해해야 하는 문제였습니다. 현재 자신의 지역을 포함해 둘러싸고 있는 총 9구역에서 불모지가 없어야하며, 물과 산, 초원이 모두 존재해야 도시를 세우기 적합한 장소입니다. 

현재 지도의 정보는 아래와 같이 숫자로 변환시켜 존재합니다.

불모지 - 0

물 - 1

산 - 2

초원 - 3

즉, 자신을 포함해 주변에 0이 존재하면 안되고, 1,2,3이 하나씩은 포함이 돼야 적합한 장소입니다. 현재 입력되는 땅이 N*N의 정사각형으로 이루어져 있기 때문에 2차원 배열을 생성하여 저장하려고 생각했습니다.

N은 10 이하의 자연수라고 했기 때문에 아래와 같이 배열을 선언했습니다.

int ground[10][10];

테스트케이스는 총 20개 이하로 구성되어 있어, 적합한 지역의 개수를 셀 count 변수의 배열은 20으로 정하고 0으로 초기화 시켜놓았습니다.

int count[20] = { 0, }; // 적합한 장소 수를 체크할 count 생성

지도 정보는 간단히 이중 for문을 통해 입력할 수 있구요.

for (int j = 0; j < N; j++) { // 지도 정보 입력
                for (int z = 0; z < N; z++) {
                    cin >> ground[j][z];
                }
            }

이제 ground 배열을 처음부터 하나씩 방문하면서, 이 위치가 적합한 지역인지 확인하기 위한 과정을 만들었습니다. bool 형으로 메소드를 만들어 조건을 충족하면 true를 출력하는 방식을 사용했습니다. 그래서 true가 나오면 조건문을 통해 count 변수를 1 증가시켜 적합한 장소의 수를 저장하도록 했습니다.

for (int j = 0; j < N; j++) {
                for (int z = 0; z < N; z++) {
                    check(j, z, N);
                    if (check(j, z, N) == true) { // 적합한 장소면 count 증가
                        count[i] += 1;
                    }
                    one = 0; two = 0; three = 0; // 전역 변수 초기화
                }
            }

이제 가장 핵심부분인 check 메소드를 확인해볼까요?

bool check(int a, int b, int N) { // 둘러싼 위치에 초원, 산, 물이 있는지 and 불모지인지 파악
 
    for (int i = (a - 1); i <= a + 1; i++) { // (a,b)일때 (a-1,b-1) ~ (a+1,b+1)구역 확인
        for (int j = (b - 1); j <= b + 1; j++) {
 
            if (i >= 0 && j >= 0 && i < N && j < N ) { // 바깥구역 제외
 
                if (ground[i][j] == 0) { // 불모지면 false
                    return false;
                }
                else if (ground[i][j] == 1) {
                    one += 1;
                }
                else if (ground[i][j] == 2) {
                    two += 1;
                }
                else if (ground[i][j] == 3) {
                    three += 1;
                }
            }
        }
    }
 
    if (one == 0 || two == 0 || three == 0) { // 초원, 산, 물이 하나라도 없으면 false
        return false;
    }
 
    return true;
}

check 메소드의 매개변수 a와 b는 ground[a][b]에 해당한다고 생각하시면 됩니다. N 변수는 지도의 영역만큼 for문을 돌리기 위해 가져와 총 3개의 매개변수를 이용했습니다.

for문을 a-1부터 a+1까지, b-1부터 b+1까지 설정한 이유는, 해당 구역 ground[a][b]를 둘러싸는 위치를 모두 확인하기 위함입니다.

이제 자신을 포함한 둘러싼 부분에 불모지에 해당하는 0 값이 나오면 적합한 구역이 아니기 때문에 바로 false 리턴하도록 했구요.

1,2,3이 나오는 지역은 one, two, three 변수를 따로 만들어 저장시키도록 만들었습니다.

한 구역의 반복문이 모두 끝나면, 지역을 저장한 one, two, three를 이용해서 물, 산, 초원의 수가 1개 이상씩 갖추고 있는지 확인했습니다. 적합한 땅이 되려면, 총 9구역에 0이 없어야하고 1, 2, 3이 하나씩은 존재해야 합니다. 만약 하나라도 존재하지 않으면 false를 리턴하고, 이 조건문이 모두 해당하지 않으면 도시를 세우기 적합한 장소이므로 true를 출력하도록 만들었습니다.

이렇게 된다면, 해당 테스트케이스마다 해당되는 적합한 장소의 수가 출력될 수 있습니다.

전체 소스 코드

#include <iostream>
 
using namespace std;
 
 
int T, N;
int ground[10][10];
int one, two, three = 0;
 
bool check(int a, int b, int N) { // 둘러싼 위치에 초원, 산, 물이 있는지 and 불모지인지 파악
 
    for (int i = (a - 1); i <= a + 1; i++) { // (a,b)일때 (a-1,b-1) ~ (a+1,b+1)구역 확인
        for (int j = (b - 1); j <= b + 1; j++) {
 
            if (i >= 0 && j >= 0 && i < N && j < N ) { // 바깥구역 제외
 
                if (ground[i][j] == 0) { // 불모지면 false
                    return false;
                }
                else if (ground[i][j] == 1) {
                    one += 1;
                }
                else if (ground[i][j] == 2) {
                    two += 1;
                }
                else if (ground[i][j] == 3) {
                    three += 1;
                }
            }
        }
    }
 
    if (one == 0 || two == 0 || three == 0) { // 초원, 산, 물이 하나라도 없으면 false
        return false;
    }
 
    return true;
}
 
int main() {
    int count[20] = { 0, }; // 적합한 장소 수를 체크할 count 생성
 
    cin >> T; //testcase
 
    for (int i = 0; i < T; i++) {
        cin >> N;
 
        if (N >= 3 && N <= 10) {
 
            for (int j = 0; j < N; j++) { // 지도 정보 입력
                for (int z = 0; z < N; z++) {
                    cin >> ground[j][z];
                }
            }
 
            for (int j = 0; j < N; j++) {
                for (int z = 0; z < N; z++) {
                    check(j, z, N);
                    if (check(j, z, N) == true) { // 적합한 장소면 count 증가
                        count[i] += 1;
                    }
                    one = 0; two = 0; three = 0; // 전역 변수 초기화
                }
            }
        }
        else {
            return 0;
        }
    }
 
    for (int i = 0; i < T; i++) {
        cout << "#" << i+1 << " " << count[i] << endl;
    }
}