출처
(사)한국소프트웨어기술인협회 소프트웨어역량연구소, 『삼성 소프트웨어 역량테스트』, 와우패스(2018-01-01), 86-103p
1. 문제
국방부에서 세 종류의 재래식 폭탄 개발에 성공하였는데, 재래식 폭탄은 상하좌우에만 영향을 미치고 각 타입마다 영향을 미치는 범위가 다르다.
- A형 폭탄은 2칸
- B형 폭탄은 2칸
- C형 폭탄은 3칸
예를 들어 [그림 1]처럼 해당 위치에 폭탄이 떨어졌을 때 영향을 받는 지역은 색으로 표시되어 있고, 아무런 영향을 받지 않으면 빈칸으로 표시되어 있다. 아무 영향을 받지 않는 지역은 총 61개 지역이다.
| X | X | ||||||||
|---|---|---|---|---|---|---|---|---|---|
| A | X | X | A | X | |||||
| X | X | X | X | ||||||
| X | X | A | X | X | |||||
| X | X | B | X | X | X | ||||
| X | X | ||||||||
| X | X | X | X | C | X | X | |||
| X | X | ||||||||
| X | A | X | X | ||||||
| X | X |
[그림 1] 지도
[그림 1]의 폭탄 위치는 A형은 (1, 0), (1, 8), (3, 4), (8, 1), B형은 (4, 2), C형은 (6, 7)이다.
(1) 문제 제시
주어진 지도에서 떨어진 폭탄으로 영향을 받지 않는 지역은 몇 개인지 구하라.
(2) 제약사항
2차원 배열의 크기 n은 5 ≤ n ≤ 50이며 폭탄의 개수는 30개 이하이다. 폭탄의 타입은 띄어쓰기 없이 쉼표를 기준으로 나눈다.
2. 입력 및 출력 형태
(1) 입력
- 테스트케이스 N (0 < N ≤ 3)
- 지도의 크기 (M X M)
- A, B, C형 폭탄의 떨어진 좌표 값(쉼표로 구분)
- ex) 0 0,3 3,5 5 –> A(0, 0), B(3, 3), C(5, 5)
(2) 입력 예
input.txt
3
7
0 0 1 5 3 5 5 6,1 1 2 4 5 2,3 2 5 5
4
0 1 1 3,2 2,2 3 3 3
5
0 0 3 4 2 4,1 2 4 2,3 2 4 4
(3) 출력
- #x n(x는 테스트케이스 번호, n은 결과)
(4) 출력 예
output.txt
#1 10
#2 1
#3 4
3. 문제 해결 방법
- 모든 행렬의 값을 0으로 초기화
- A, B, C의 좌표를 입력받아 해당 값을 1로 변환
- 0의 개수 구하기
4. 해결 프로그램
input.txt는 미리 만들어 놓았다.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int get(int i, int j, char **board, int num) { // 범위 체크 함수
if (i < 0 || j < 0 || i >= num || j >= num)
return 0;
return 1;
}
int matrix(char **board, int num) { // A, B, C형 폭탄의 범위 계산
int i, j; // 반복문 인덱스
int remainder = 0; // 남은 지역 수
for (i = 0; i < num; i++) {
for (j = 0; j < num; j++) {
switch (board[i][j]) {
case 'C': // C형 폭탄의 범위만큼 커버
if (get(i - 3, j, board, num) == 1 && board[i - 3][j] == '0')
board[i - 3][j] = '1';
if (get(i, j - 3, board, num) == 1 && board[i][j - 3] == '0')
board[i][j - 3] = '1';
if (get(i + 3, j, board, num) == 1 && board[i + 3][j] == '0')
board[i + 3][j] = '1';
if (get(i, j + 3, board, num) == 1 && board[i][j + 3] == '0')
board[i][j + 3] = '1';
case 'B': // B형 폭탄의 범위만큼 커버
if (get(i - 2, j, board, num) == 1 && board[i - 2][j] == '0')
board[i - 2][j] = '1';
if (get(i, j - 2, board, num) == 1 && board[i][j - 2] == '0')
board[i][j - 2] = '1';
if (get(i + 2, j, board, num) == 1 && board[i + 2][j] == '0')
board[i + 2][j] = '1';
if (get(i, j + 2, board, num) == 1 && board[i][j + 2] == '0')
board[i][j + 2] = '1';
case 'A': // A형 폭탄의 범위만큼 커버
if (get(i - 1, j, board, num) == 1 && board[i - 1][j] == '0')
board[i - 1][j] = '1';
if (get(i, j - 1, board, num) == 1 && board[i][j - 1] == '0')
board[i][j - 1] = '1';
if (get(i + 1, j, board, num) == 1 && board[i + 1][j] == '0')
board[i + 1][j] = '1';
if (get(i, j + 1, board, num) == 1 && board[i][j + 1] == '0')
board[i][j + 1] = '1';
}
}
}
printf("\n\n");
for (i = 0; i < num; i++) {
for (j = 0; j < num; j++) {
printf("%c ", board[i][j]);
if (board[i][j] == '0')
remainder++;
}
printf("\n");
}
return remainder; // 남은 지역 수 반환
}
int main(void) {
FILE *in, *out;
in = fopen("input.txt", "r");
out = fopen("output.txt", "w");
char tempNum[50], temp[100]; // 파일입출력
char **arrNum; // 2차원 배열
char *cutStr[3]; // 파일입출력
int num, size[3]; // 2차원 배열의 크기, A, B, C형 폭탄의 수
int pt[3][8] ={0, }, ptx, pty; // 좌표 변수
int i, j, k; // 반복문 인덱스
int remainder, testNum; // 남은 지역 수, 테스트케이스
fgets(temp, 100, in);
testNum = atoi(temp);
for (k = 0; k < testNum; k++) {
printf("#%d", k + 1);
fgets(tempNum, 50, in);
fgets(temp, 100, in);
num = atoi(tempNum);
arrNum = (char **)malloc(sizeof(char *) * num); // 배열 크기 할당
for (i = 0; i < num; i++)
arrNum[i] = (char *)malloc(sizeof(char) * num);
for (i = 0; i < num; i++)
for (j = 0; j < num; j++)
arrNum[i][j] = '0';
cutStr[0] = strtok(temp, ","); // A형
cutStr[1] = strtok(NULL, ","); // B형
cutStr[2] = strtok(NULL, "\n"); // C형
for (i = 0; i < 3; i++) // 위치선정
size[i] = strlen(cutStr[i]);
for (i = 0; i < 3; i++) { // 좌표
pt[i][0] = atoi(strtok(cutStr[i], " "));
for (j = 1; j <= (size[i] - 1) / 2; j++)
pt[i][j] = atoi(strtok(NULL, " "));
}
printf(" 지도의 크기: %d\n", num);
printf("폭탄이 떨어진 위치\n");
for (i = 0; i < 3; i++) {
printf("%c형 폭탄: ", 65 + i);
for (j = 0; j <= (size[i] - 1) / 2; j++)
printf("%d ", pt[i][j]);
printf("\n");
}
printf("\n");
for (i = 0; i < 3; i++) {
for (j = 0; j <= (size[i] - 1) / 2; j++) {
if (i == 0) {
if ((i + j) % 2 == 0)
ptx = pt[i][j];
else {
pty = pt[i][j];
arrNum[ptx][pty] = 'A';
}
} else if (i == 1) {
if ((i + j) % 2 == 0) {
pty = pt[i][j];
arrNum[ptx][pty] = 'B';
} else
ptx = pt[i][j];
} else {
if ((i + j) % 2 == 0)
ptx = pt[i][j];
else {
pty = pt[i][j];
arrNum[ptx][pty] = 'C';
}
}
}
}
for (i = 0; i < num; i++) {
for (j = 0; j < num; j++)
printf("%c ", arrNum[i][j]);
printf("\n");
}
remainder = matrix(arrNum, num); // 함수 호출 후 남은 지역 수 반환
printf("\n커버되지 않은 지역의 수: %d \n \n", remainder);
fprintf(out, "#%d %d\n", k + 1, remainder);
}
fclose(in);
fclose(out);
return 0;
}
5. 실행 결과
#1 지도의 크기: 7
폭탄이 떨어진 위치
A형 폭탄: 0 0 1 5 3 5 5 6
B형 폭탄: 1 1 2 4 5 2
C형 폭탄: 3 2 5 5
A 0 0 0 0 0 0
0 B 0 0 0 A 0
0 0 0 0 B 0 0
0 0 C 0 0 A 0
0 0 0 0 0 0 0
0 0 B 0 0 C A
0 0 0 0 0 0 0
A 1 1 0 1 1 0
1 B 1 1 1 A 1
0 1 1 1 B 1 1
1 1 C 1 1 A 1
0 0 1 0 1 1 1
1 1 B 1 1 C A
0 0 1 0 0 1 1
커버되지 않은 지역의 수: 10
#2 지도의 크기: 4
폭탄이 떨어진 위치
A형 폭탄: 0 1 1 3
B형 폭탄: 2 2
C형 폭탄: 2 3 3 3
0 A 0 0
0 0 0 A
0 0 B C
0 0 0 C
1 A 1 1
0 1 1 A
1 1 B C
1 1 1 C
커버되지 않은 지역의 수: 1
#3 지도의 크기: 5
폭탄이 떨어진 위치
A형 폭탄: 0 0 3 4 2 4
B형 폭탄: 1 2 4 2
C형 폭탄: 3 2 4 4
A 0 0 0 0
0 0 B 0 0
0 0 0 0 A
0 0 C 0 A
0 0 B 0 C
A 1 1 0 0
1 1 B 1 1
0 0 1 1 A
1 1 C 1 A
1 1 B 1 C
커버되지 않은 지역의 수: 4
Comments