[Hive Helsinki / Piscine] Rush01
Rush01은 주어진 조건에 따라 1, 2, 3, 4의 높이를 가진 막대를 알맞게 배치하는 문제이다. 문제를 이해하는 데까지도 좀 어렵다고 느꼈고, 풀이하는 데는 더욱 오래 걸렸다. 결국 마지막에 사소한 실수와 malloc check를 하지 않은 문제들로 인해서 fail을 받았지만, 결국 출력을 할 수 있게 만드는 데에는 성공했다. 여기서 적는 방법은 피신 이후 내가 오류나 효율성을 고려해서 코드를 수정한 내용이다. 따라서 피신에서의 형식이나 규칙에 어긋나는 부분(금지 함수를 쓰는 등의 제한을 어긴 것은 아니지만, 띄어쓰기나 인자, row 수 제한 등의 규칙은 신경 쓰지 않았다)이 있을 수 있고, 따라서 문제의 접근 방식만 참고하는 편이 좋을 것 같다.
예시 input으로 문제에 대한 설명부터 해보겠다. 주어진 예시 인풋은 다음과 같다.
./rush-01 "4 3 2 1 1 2 2 2 4 3 2 1 1 2 2 2" | cat -e
숫자는 순서대로 "col1up col2up col3up col4up col1down col2down col3down col4down row1left row2left row3left row4left row1right row2right row3right row4right"를 의미한다. 이를 그림으로 표현하면 아래와 같다.
이렇게 인풋이 주어지면 주어진 방향에서 봤을 때, 해당 숫자만큼의 막대만 보여야 한다. 더 긴 막대를 짧은 막대 앞에 배치하면 짧은 막대는 가려지므로 이를 이용해서 보이는 막대의 수를 조절하는 것이다.
이렇게 input이 주어졌을 때 출력은 아래와 같다. 숫자 하나하나가 위 그림에서 각 칸에 들어갈 숫자이다.
./rush-01 "4 3 2 1 1 2 2 2 4 3 2 1 1 2 2 2" | cat -e
1 2 3 4$
2 3 4 1$
3 4 1 2$
4 1 2 3$
내가 이 문제에 접근한 방식은 Back-tracking(백트래킹) 알고리즘을 활용한 풀이이다. Back-tracking은 모든 경우의 수를 하나하나 체크하는 Brute force 알고리즘에 효율성을 더한 방식이다. Brute force가 중간에 해당 경우가 가능한지 여부를 체크하지 않고, 끝까지 가서 체크한다면 Back-tracking은 중간중간 해당 경우가 가능한지를 확인하여 만약 해당 단계에서 이미 불가능한 경우라면 멈추고 다른 경우를 탐색한다. 나는 여기서 column up, row left 조건 그리고 중복여부을 확인하면서 칸 하나하나를 채웠고, 한 row를 완성하면 row right를 확인하고, table 전체를 완성한 후 column down을 확인하는 방식을 취했다.
예를 들어, 가장 첫번째 칸(0, 0)을 채운다면 위 예시에서는 column up 방향에서 보이는 개수가 4를 넘지 않는지, row left 방향에서 보이는 개수가 4를 넘지 않는지 확인할 것이다. 두 번째 칸(0, 1)에서는 첫 번째 칸과 중복되지 않는지, column up 방향에서 보이는 개수가 3을 넘지 않는지, 그리고 row left 방향에서 보이는 개수가 4를 넘지 않는지 확인할 것이다. 1 2 3 4가 완성된다면, row left 방향에서 보이는 개수가 1이 맞는지를 확인할 것이다.
우선 헤더 파일을 통해 전체적인 구조를 이야기하자면, 총 세 개의 파일로 나눠서 작성했다. 하지만 어떤 파일에 어떤 함수가 있는지는 크게 중요하지 않기 때문에 이후 설명하는 과정에서는 함수 단위로 소개해보려 한다.
/* main.h 파일 */
#ifndef MAIN_H
#define MAIN_H
#include <stdlib.h>
#include <unistd.h>
// rush-01.c
int *make_input(char **input);
int put_res(int cur_col, int cur_row, int **input, int **res);
void print_res(int wid, int hei, int *res);
// check-elem.c
int check_rowl(int cur_col, int cur_row, int *res, int r_condition);
int check_colu(int cur_col, int cur_row, int *res, int c_condition);
// check-table.c
int check_table(int **input, int *res);
int check_rowr(int cur_row, int r_condition, int *res);
int check_cold(int cur_col, int c_condition, int *res);
#endif
메인 함수를 먼저 보면 아래와 같다. 우선 터미널로 부터 받은 input의 개수가 2개가 아니라면 우리가 받아야 할 문자열보다 더 많이 받거나 모자라게 받았다는 의미이다. 따라서 에러를 출력해 주고 프로그램을 종료한다.
그리고 나서는 받은 문자열을 사용하기 편하게 정리하여 배열에 저장해 준다. 앞서 언급했듯, 입력되는 input은 "col1up col2up col3up col4up col1down col2down col3down col4down row1left row2left row3left row4left row1right row2right row3right row4right"와 같은 형식을 가진다. 따라서 input[0][0~3]에 colup 정보들을, input[0][4~7]에 coldown 정보들을, input[1][0~3]에 rowleft 정보들을, input[1][4~7]에 rowright 정보들을 각각 int type으로 변환하여 저장해 준다. 이렇게 정리하는 과정은 make_input() 함수가 수행한다.
결과값을 저장할 res 배열은 1차원 배열로 선언해 줬는데, res 배열을 완성하기 위해 여러 함수를 사용할 것이기 때문에, 투포인터로 사용하는 번거로움을 막기 위해 이렇게 선언했다. 1차원으로 선언하고, (x, y) 위치의 값이 (x * 4 + y)의 인덱스를 가지도록 하여 2차원 배열처럼 활용했다.
그리고는 바로 이 프로그램에서 가장 중요한 역할을 수행하는 put_res() 함수로 진입하여, 해당 함수가 1을 리턴하면 print_res() 함수를 이용해 결과값을 출력하고 아니면 Error를 출력한다.
int main(int argc, char **argv)
{
int **input;
int *res;
// input 형식이 알맞지 않다면 Error 출력하고 프로그램 종료
if (argc != 2)
{
write(1, "Error\n", 6);
return (0);
}
// input을 받을 input 2차원 배열 선언 & 메모리 할당
// input[0]의 0~3까지는 colup 정보, 4~7까지는 coldown 정보
// input[1]의 0~3까지는 rowleft 정보, 4~7까지는 rowright 정보
input = (int **)malloc(sizeof(int *) * 2);
if (input == NULL)
{
write(1, "Error\n", 6);
return (0);
}
// 결과값을 저장할 res 1차원 배열 선언하고 메모리 할당
// [x, y] 위치의 결과가 (x * 4 + y)에 저장, 즉 2차원인 배열을 1차원화 하여 저장
res = (int *)malloc(sizeof(int) * 16);
if (res == NULL)
{
write(1, "Error\n", 6);
free(input);
return (0);
}
// input을 입력받아 input 배열에 넣어주기
input[0] = make_input(argv + 1);
if (input[0] == NULL)
{
free(input);
free(res);
write(1, "Error\n", 6);
return (0);
}
input[1] = make_input(argv + 1);
if (input[0] == NULL)
{
free(res);
free(input[0]);
free(input);
write(1, "Error\n", 6);
return (0);
}
// put_res의 결과값이 있을 경우 이를 출력하고, 결과가 없다면 오류를 출력
if (put_res(0, 0, input, &res))
print_res(4, 4, res);
else
write(1, "Error\n", 6);
free(input[0]);
free(input[1]);
free(input);
free(res);
}
앞서 main 함수 설명에서 언급했듯, make_input() 함수는 주어진 16개의 숫자로 구성된 문자열을 int type으로 변환하여 배열에 저장하는 역할을 한다. main 함수에서 선언된 input 2차원 배열 중 input[0]에는 column 관련 정보가, input[1]에는 row 관련 정보가 들어갈 것이다. 따라서 해당 함수에서는 8개의 숫자를 크기가 8인 1차원 배열에 저장하여 리턴한다. 결국 이 함수가 두 번 호출되어 column관련 정보와 row 관련 정보를 각각 저장하는 것이다.
input 인자는 입력받은 16개의 숫자로 구성된 문자열이 될 것이다. 이는 1차원 배열이지만 two pointer로 입력받는다. 이유는 input[0]에 column 관련 정보인 8개의 숫자를 저장한 후, 다시 함수를 호출할 때는 그다음부터 input[1]에 넣어야 해서 저장된 숫자 다음으로 input 포인터가 가리키고 있는 메모리 위치를 넘겨주기 위함이다.
우선 배열에 메모리를 할당해주고, 문자열에 1~4 사이의 숫자가 있을 때만 입력해 준다. 만약 1~4 사이의 숫자도, 공백도 아닌 다른 문자가 있다면 이는 잘못된 입력을 의미하므로 NULL을 리턴해준다. 만약 8개의 숫자를 다 채울 동안, 1~4 사이 숫자 혹은 공백만 존재한다면 정상적으로 8개의 숫자를 채운 res 배열을 리턴해주면서 함수를 마무리한다.
int *make_input(char **input)
{
int x;
int *res;
// 정리된 input 결과를 담을 res 배열 메모리 할당
res = (int *)malloc(sizeof(int) * 8);
if (res == NULL) return NULL;
x = 0;
// col, row에 맞는 정보만 담기 위해서 8개까지만 담음
while (**input && (x < 8))
{
if ((**input >= '1') && (**input <= '4'))
{
res[x] = **input - '0';
x++;
}
else if (**input != ' ') // 입력받은 문자가 1~4의 숫자도, 공백도 아니면 NULL을 리턴 (잘못된 입력)
return NULL;
++(*input);
}
return (res);
}
print_res() 함수는 완성된 결과가 저장된 res 배열을 4x4 크기로 알맞게 출력해 주는 역할을 한다. 앞서 언급했듯, res 배열은 1차원 배열이지만, 2차원 배열처럼 동작한다. 따라서 각자 위치에 맞게 잘 출력해줘야 한다. 우선 메인 함수에서 wid 인자와 hei 인자가 각각 4로 설정되어 시작될 것이다. (bonus로 4x4 이상의 배열도 만들어보려다가 실패한 흔적이라고 볼 수 있다...) 그리고 완성된 res 배열도 인자로 함께 주어진다.
함수 안에 선언된 w가 좌표로 보면 y의 역할을 하여, wid-1의 최댓값을 가질 것이고, h가 좌표 x의 역할을 하여 hei-1의 최대값을 가질 것이다. 따라서 h는 0~(hei-1)까지 순회하고, w는 0~(wei-1)까지 순회하며 각 요소 하나하나를 출력하고, h 변수가 1씩 증가할 때마다 new line character를 출력해 주면, 우리가 아는 일반적인 4x4 정사각형 모양의 출력을 얻을 수 있다.
주의할 점은 w가 3인 경우, 즉 해당 row 내 마지막 요소인 경우는 공백을 출력하면 안 되므로, 조건문으로 이를 삽입해줘야 한다는 점이다. 공백이 어차피 보이지 않는데 상관이 없지 않냐고 생각할 수 있지만, 문제에서 주어진 입력도 그렇고 평가자도 평가할 때 cat -e command를 사용하여 출력하기 때문에 공백이 눈에 잘 띈다.
void print_res(int wid, int hei, int *res) // wid, hei 인자 = 주어진 res 배열의 너비 / 높이
{
// w, h 변수 = 너비 / 높이를 순회할 변수
int w;
int h;
char c;
h = 0;
while (h < hei)
{
w = 0;
while (w < wid)
{
// [h, w] 위치의 인자는 배열의 (h * wid + w) 인덱스에 저장되어 있음
c = res[h * wid + w] + '0';
write(1, &c, 1);
if (w != 3) // row 내 마지막 요소일 경우는 공백을 출력하면 안됨
write(1, " ", 1);
w++;
}
write(1, "\n", 1);
h++;
}
}
put_res()는 이 프로그램의 핵심적인 함수라고 볼 수 있다. 이 문제의 백트래킹 알고리즘의 주축이 되는 함수이다. put_res() 함수는 재귀함수(recursive function)으로 구현되어 백트래킹을 구현한다.
재귀의 중단 조건은 row가 3, column이 4 이상이 되는, 즉 4x4의 table이 완성되는 것이다. table이 완성되면 check_table() 함수를 통해 마지막으로 확인해야 할 column down 조건을 확인한 후, 조건을 충족한다면 1 아니라면 0을 리턴하게 된다. 만약 모든 경우의 수를 시도해보지 않았다면, 다시 이전으로 돌아가 시도해보지 않았던 경우들을 시도해 보게 된다.
만약 하나의 row가 완성되었다면 check_rowr() 함수로 row right 조건을 확인하고, 만약 충족한다면 put_row() 함수를 호출하여 다음 row로 넘어가고, 그렇지 않다면 0을 리턴하여, 이 경우에 대한 탐색을 중단할 것을 알린다. 그렇다면 현재 row에 다른 가능한 경우들을 시도해 보거나, 현재 row에 남은 경우의 수가 없다면 이전 row로 돌아가서 아직 확인하지 않은 남은 경우들에 대한 탐색을 시작할 것이다.
만약 둘 다 아직 다 채워지지 않은 경우라면, (cur_row, cur_col) 위치에 어떤 수가 들어갈 수 있을지에 대한 탐색을 시작해야 한다. 결괏값으로는 1~4의 정수만 들어갈 수 있으므로, while문을 통해 1에서 4까지 순회하며 가능한 경우를 찾는다. 우선 res 배열에서 현재 위치에 해당하는 index(cur_row * 4 + cur_col)에 현재 탐색 중인 값(i)을 넣는다. 그 상태로 check_rowl() 함수와 check_colu() 함수를 이용하여 row left 조건과 column up 조건을 이미 어기지는 않았는지를 확인한다. 만약 이미 어겼다면 다음 i로 넘어갈 것이고, 그렇지 않다면 현재 i를 res 배열에 넣은 상태로 다음 cur_col으로 넘어가서 탐색을 계속하게 된다. 또한, put_res() 함수를 호출하여 다음 cur_col으로 넘어갔더라도, 해당 put_res() 함수가 0을 리턴하면, 즉 그 경우가 불가능하다고 판단된다면, 넘어가서 다음 i를 탐색할 수 있다. 이것이 앞서 언급했던 "만약 모든 경우의 수를 시도해보지 않았다면, 다시 이전으로 돌아가 시도해보지 않았던 경우들을 시도"할 수 있는 이유이다.
이렇게 while문으로 1에서 4까지를 모두 순회하였음에도 알맞은 경우를 찾지 못한 경우는 최종적으로 0을 리턴하게 된다.
int put_res(int cur_col, int cur_row, int **input, int **res)
{
int i;
// row 단위로 넣던 res 배열이 완성되면 column 단위로 확인
if ((cur_row == 3) && (cur_col >= 4))
return (check_table(input, *res));
// row 하나가 완성되면 다음 row로 보내주기
if (cur_col >= 4)
{
if (check_rowr(cur_row, input[1][cur_row + 4], *res))
return (put_res(0, cur_row + 1, input, res));
return (0);
}
// 1부터 4까지 현재 위치에 알맞은 숫자를 찾으면 다음 column으로 넘어가도록 재귀함수 호출
i = 1;
while (i <= 4)
{
(*res)[cur_row * 4 + cur_col] = i++;
if (check_rowl(cur_col, cur_row, *res, input[1][cur_row]) && check_colu(cur_col, cur_row, *res, input[0][cur_col]))
{
if (put_res(cur_col + 1, cur_row, input, res))
return (1);
}
}
// 결과적으로 해당 위치에 맞는 숫자를 못찾으면 0 리턴
return (0);
}
이렇게 전체 흐름의 핵심이 되는 put_res() 함수를 살펴보았으니, 이제 각 조건들을 확인하는 함수들을 보려고 한다. 간단히 조건을 처리하는 방법부터 언급하려 한다. 보통 컴퓨터로 하여금 문제를 해결하게 하는 방식을 찾을 때, 내 뇌가 어떤 프로세스를 거쳐 이런 결론을 냈는지를 단계를 나눠 생각해보려 한다. 이 문제 역시 그런 방식으로 결론을 냈다. 생각보다 우리 뇌는 이미 익숙해진 프로세스를 무의식적으로 수행하거나 시각적으로 규칙을 빠르게 찾아내기 때문에, 내가 어떤 과정을 거쳐 이 결과에 도달했는지 떠올리기 어려울 때가 있다. 그래서 이런 문제를 풀 때는 왜 이렇게 판단했지? 와 같이 스스로 왜?라는 질문을 끊임없이 하게 되는 것 같다.
이 문제의 경우에는 최댓값이 몇 번 바뀌는지를 세는 것으로 현재 몇 개의 기둥이 보이는지를 확인했다. 우리의 시야에 뒤에 있는 기둥이 보이려면 앞에 있는 기둥의 높이를 뛰어넘는 기둥이어야 한다. 따라서 주어진 조건의 시야에서 가장 가까운 기둥에서부터 시작해서 기둥 높이의 최대값이 몇 번 바뀌는지를 카운트하면, 몇 개의 기둥이 보이는지를 확인할 수 있다. 그리고 row나 column이 완성되기 전에는 보이는 기둥의 개수가 이미 조건을 넘어버리지는 않았는지를 확인하고, 완성된 경우는 조건과 일치하는지를 확인한다.
그리고 앞선 코드들에서 row left와 column up 조건의 경우는 아직 row나 column이 완성되기 전에 확인하면서 나아가는데, row right나 column down의 경우 row나 column이 완성된 후 체크하는 것도 위의 방식을 사용하기 때문이다. 우리가 left, up 방향부터 채우기 시작하는데, 완성되기 전에 right이나 down 방향에서 조건을 넘어가는지를 체크하면 오류가 발생할 수 있다. 예를 들어 left 조건이 1인데 3 2까지 채웠다면 이미 조건이 위배된 것이다. 하지만 만약 3 2 1 4가 된다면 4가 앞선 기둥들을 모두 가려버리기 때문에 left 조건에 맞는 배열이다. 그런데 row 완성 전 left 조건을 확인했다면 이 경우를 완성해보지 못하게 될 것이다. 따라서 left와 up은 요소 하나하나를 채우면서, right와 down은 row나 column이 모두 완성된 후에 확인하는 것이다.
먼저 check_rowl() 함수, 즉 row left 조건을 확인하는 함수이다. 만약 cur_col이 0이라면 아직 해당 row에 요소가 하나밖에 채워져 있지 않다는 뜻이므로, 충족할 조건이 없을 것이다. 따라서 해당 경우는 무조건 가능하다는 의미로 1을 리턴하고 함수를 종료한다.
아니라면 현재 row의 첫 번째 요소부터 현재 요소까지를 순회하며 조건을 이미 위배하지는 않았는지를 확인해야 한다. 현재 row의 첫번째 요소부터 순회할 j 변수를 선언해 주고, max 값이 몇 번 바뀌는지 확인해야 하니 max 변수도 0으로 초기화해 준다. 그리고 max 값이 몇 번 바뀌는지의 정보를 넣을 count 변수도 0으로 초기화해준다.
그리고 0~cur_col까지 순회를 하며 ① 중복 체크, ② 몇 개의 기둥이 보이는지 count를 해준다. 중복되는 요소가 있다면 바로 0을 리턴해주어, 이 경우가 불가능하다는 것을 알린다. while문을 통해 순회를 마치면 count 변수에 left 방향에서 몇 개의 기둥이 보이는지의 정보가 저장된다.
만약 아직 row가 완성되지 않은 경우, count 변수가 이미 row left 조건(r_condition)을 초과하지 않았는지만 확인해 주고, 초과했다면 0을 리턴해준다. 만약 row가 완성된 경우(cur_col == 3), count 변수에 저장된 값이 row left 조건과 일치하는지를 확인하여, 일치하지 않다면 0을 리턴해준다.
이 모든 조건들을 통과하고 마지막에 도달했다면 결국 1을 리턴하여 해당 경우를 지속해도 됨을 알린다.
int check_rowl(int cur_col, int cur_row, int *res, int r_condition)
{
int cur;
int j;
int max;
int count;
if (cur_col == 0) return (1);
j = 0;
max = 0; // max가 바뀐다는 것 => 하나의 기둥이 더 보이는 것
count = 0; // max가 바뀌는 횟수를 셈 => 몇 개의 기둥이 보이는지 셈
while (j <= cur_col)
{
cur = res[cur_row * 4 + j];
if (j < cur_col && res[cur_row * 4 + cur_col] == cur)
return (0); // 중복 체크
if (cur > max)
{
max = cur;
count++;
}
j++;
}
// 이미 조건으로 주어진 횟수를 넘어버렸다면 0을 리턴 아니면 1을 리턴
if (count > r_condition)
return (0);
// 마지막 column이라면 정확히 일치하는지 확인해야 함
if (cur_col == 3 && count != r_condition)
return (0);
return (1);
}
check_colu() 함수는 check_rowl() 함수와 구조가 동일하다. 다만 column을 옮겨가며 row 전체를 탐색했던 check_rowl() 함수와는 달리 row를 옮겨가며 column 전체를 탐색한다는 것이 유일하게 다른 점이다.
int check_colu(int cur_col, int cur_row, int *res, int c_condition)
{
int cur;
int j;
int max;
int count;
if (cur_row == 0) return 1;
j = 0;
max = 0; // max가 바뀐다는 것 => 하나의 기둥이 더 보이는 것
count = 0; // max가 바뀌는 횟수를 셈 => 몇 개의 기둥이 보이는지 셈
while (j <= cur_row)
{
cur = res[j * 4 + cur_col];
if (j < cur_row && res[cur_row * 4 + cur_col] == cur)
return (0); // 중복 체크
if (cur > max)
{
max = cur;
count++;
}
j++;
}
// 이미 조건으로 주어진 횟수를 넘어버렸다면 0을 리턴 아니면 1을 리턴
if (count > c_condition)
return (0);
// 마지막 row라면 정확히 일치하는지 확인해야 함
if (cur_row == 3 && count != c_condition)
return (0);
return (1);
}
다음은 check_rowr() 함수이다. 앞서 언급했듯, row right 조건과 column down 조건은 row나 column을 모두 완성한 후 확인한다. 따라서 다른 요소는 모두 같지만, 중복 체크를 하지 않는다는 점(앞서 row left 조건이나 column up 조건을 확인할 때 중복까지 함께 확인하며 요소를 채워왔기 때문에 row나 column이 완성되었을 때는 중복이 발생하지 않는다)과 조건을 넘어가는지가 아니라 조건에 완벽히 일치하는지 확인하는 것이 다른 점이다. 즉 앞선 check_rowl() 함수와 check_cold()은 row나 column 완성 전에 이미 조건을 위배하게 되지 않는지에 대한 확인이라면, check_rowr()과 check_cold()은 완성된 row나 column이 조건을 충족하는지에 대한 확인이다. 몇 개의 기둥이 보이는지 확인하는 방식은 위 check_rowl() 함수와 동일하다.
int check_rowr(int cur_row, int r_condition, int *res)
{
int i;
int max;
int count;
i = 3;
max = 0;
count = 0;
while (i >= 0)
{
if (res[cur_row * 4 + i] > max)
{
max = res[cur_row * 4 + i];
count++;
}
i--;
}
if (count != r_condition)
return (0);
return (1);
}
마지막으로 check_table() 함수와 check_cold() 함수이다. check_table() 함수는 column 단위로 확인하는 check_cold() 함수를 각 column에 적용하여 table 전체를 확인하도록 돕는 helper 함수이다. 이전까지 하나의 열, 행 단위로 확인했던 다른 check 함수와는 달리 column down 함수의 경우 table 전체를 확인해야 하므로, 이 함수를 사용한다. 이렇게 하면 check_cold()도 다른 함수와 동일한 구조를 가지게 만들어서 활용이 가능하다. check_cold() 함수는 check_rowr()와 동일한 구조를 가진다.
int check_table(int **input, int *res)
{
int c;
// 전체 column 체크
c = 0;
while (c < 4)
{
if (!check_cold(c, input[0][c + 4], res))
return (0);
c++;
}
return (1);
}
int check_cold(int cur_col, int c_condition, int *res)
{
int i;
int max;
int count;
i = 3;
max = 0;
count = 0;
while (i >= 0)
{
if (res[i * 4 + cur_col] > max)
{
max = res[i * 4 + cur_col];
count++;
}
i--;
}
if (count != c_condition)
return (0);
return (1);
}
이렇게 모든 함수를 완성했고, 문제에 제시된 예시 case와 내가 직접 만들어 본 몇 가지 case에서 모두 적절하게 동작하는 것을 확인했다. 하지만 rush project를 실제로 피신에서 수행할 때는 몇 가지 문제로 인해서 fail을 받았으니, 해당 코드를 사용해도 pass 할 것이라는 보장은 없다. 따라서 참고만 해주시기를 다시 당부드린다.
아래는 파일 별로 저장된 전체 코드와 이를 컴파일할 Makefile 코드이다.
// main.h
#ifndef MAIN_H
#define MAIN_H
#include <stdlib.h>
#include <unistd.h>
#include <stdio.h>
// rush-01.c
int *make_input(char **input);
int put_res(int cur_col, int cur_row, int **input, int **res);
void print_res(int wid, int hei, int *res);
// check-elem.c
int check_rowl(int cur_col, int cur_row, int *res, int r_condition);
int check_colu(int cur_col, int cur_row, int *res, int c_condition);
// check-table.c
int check_table(int **input, int *res);
int check_rowr(int cur_row, int r_condition, int *res);
int check_cold(int cur_col, int c_condition, int *res);
#endif// rush-01.c
#include "main.h"
int *make_input(char **input)
{
int x;
int *res;
// 정리된 input 결과를 담을 res 배열 메모리 할당
res = (int *)malloc(sizeof(int) * 8);
if (res == NULL) return NULL;
x = 0;
// col, row에 맞는 정보만 담기 위해서 8개까지만 담음
while (**input && (x < 8))
{
if ((**input >= '1') && (**input <= '4'))
{
res[x] = **input - '0';
x++;
}
else if (**input != ' ') // 입력받은 문자가 1~4의 숫자도, 공백도 아니면 NULL을 리턴 (잘못된 입력)
return NULL;
++(*input);
}
return (res);
}
// row 단위로 넣고 column 단위로 마지막에 확인
int put_res(int cur_col, int cur_row, int **input, int **res)
{
int i;
// row 단위로 넣던 res 배열이 완성되면 column 단위로 확인
if ((cur_row == 3) && (cur_col >= 4))
return (check_table(input, *res));
// row 하나가 완성되면 다음 row로 보내주기
if (cur_col >= 4)
{
if (check_rowr(cur_row, input[1][cur_row + 4], *res))
return (put_res(0, cur_row + 1, input, res));
return (0);
}
// 1부터 4까지 현재 위치에 알맞은 숫자를 찾으면 다음 column으로 넘어가도록 재귀함수 호출
i = 1;
while (i <= 4)
{
(*res)[cur_row * 4 + cur_col] = i++;
if (check_rowl(cur_col, cur_row, *res, input[1][cur_row]) && check_colu(cur_col, cur_row, *res, input[0][cur_col]))
{
if (put_res(cur_col + 1, cur_row, input, res))
return (1);
}
}
// 결과적으로 해당 위치에 맞는 숫자를 못찾으면 0 리턴
return (0);
}
// 결과값이 저장된 res 배열을 알맞게 출력하는 함수
void print_res(int wid, int hei, int *res) // wid, hei 인자 = 주어진 res 배열의 너비 / 높이
{
// w, h 변수 = 너비 / 높이를 순회할 변수
int w;
int h;
char c;
h = 0;
while (h < hei)
{
w = 0;
while (w < wid)
{
// [h, w] 위치의 인자는 배열의 (h * wid + w) 인덱스에 저장되어 있음
c = res[h * wid + w] + '0';
write(1, &c, 1);
if (w != 3) // row 내 마지막 요소일 경우는 공백을 출력하면 안됨
write(1, " ", 1);
w++;
}
write(1, "\n", 1);
h++;
}
}
int main(int argc, char **argv)
{
int **input;
int *res;
// input 형식이 알맞지 않다면 Error 출력하고 프로그램 종료
if (argc != 2)
{
write(1, "Error\n", 6);
return (0);
}
// input을 받을 input 2차원 배열 선언 & 메모리 할당
// input[0]의 0~3까지는 colup 정보, 4~7까지는 coldown 정보
// input[1]의 0~3까지는 rowleft 정보, 4~7까지는 rowright 정보
input = (int **)malloc(sizeof(int) * 16);
if (input == NULL)
{
write(1, "Error\n", 6);
return (0);
}
// 결과값을 저장할 res 1차원 배열 선언하고 메모리 할당
// [x, y] 위치의 결과가 (x * 4 + y)에 저장, 즉 2차원인 배열을 1차원화 하여 저장
res = (int *)malloc(sizeof(int) * 16);
if (res == NULL)
{
write(1, "Error\n", 6);
free(input);
return (0);
}
// input을 입력받아 input 배열에 넣어주기
input[0] = make_input(argv + 1);
if (input[0] == NULL)
{
free(input);
free(res);
write(1, "Error\n", 6);
return (0);
}
input[1] = make_input(argv + 1);
if (input[0] == NULL)
{
free(res);
free(input[0]);
free(input);
write(1, "Error\n", 6);
return (0);
}
// put_res의 결과값이 있을 경우 이를 출력하고, 결과가 없다면 오류를 출력
if (put_res(0, 0, input, &res))
print_res(4, 4, res);
else
{
write(1, "Error\n", 6);
return (0);
}
free(input[0]);
free(input[1]);
free(input);
free(res);
}// check-elem.c
#include "main.h"
int check_rowl(int cur_col, int cur_row, int *res, int r_condition)
{
int cur;
int j;
int max;
int count;
if (cur_col == 0) return (1);
j = 0;
max = 0; // max가 바뀐다는 것 => 하나의 기둥이 더 보이는 것
count = 0; // max가 바뀌는 횟수를 셈 => 몇 개의 기둥이 보이는지 셈
while (j <= cur_col)
{
cur = res[cur_row * 4 + j];
if (j < cur_col && res[cur_row * 4 + cur_col] == cur)
return (0); // 중복 체크
if (cur > max)
{
max = cur;
count++;
}
j++;
}
// 이미 조건으로 주어진 횟수를 넘어버렸다면 0을 리턴 아니면 1을 리턴
if (count > r_condition)
return (0);
// 마지막 column이라면 정확히 일치하는지 확인해야 함
if (cur_col == 3 && count != r_condition)
return (0);
return (1);
}
int check_colu(int cur_col, int cur_row, int *res, int c_condition)
{
int cur;
int j;
int max;
int count;
if (cur_row == 0) return 1;
j = 0;
max = 0; // max가 바뀐다는 것 => 하나의 기둥이 더 보이는 것
count = 0; // max가 바뀌는 횟수를 셈 => 몇 개의 기둥이 보이는지 셈
while (j <= cur_row)
{
cur = res[j * 4 + cur_col];
if (j < cur_row && res[cur_row * 4 + cur_col] == cur)
return (0); // 중복 체크
if (cur > max)
{
max = cur;
count++;
}
j++;
}
// 이미 조건으로 주어진 횟수를 넘어버렸다면 0을 리턴 아니면 1을 리턴
if (count > c_condition)
return (0);
// 마지막 row라면 정확히 일치하는지 확인해야 함
if (cur_row == 3 && count != c_condition)
return (0);
return (1);
}// check-table.c
#include "main.h"
int check_table(int **input, int *res)
{
int c;
// 전체 column 체크
c = 0;
while (c < 4)
{
if (!check_cold(c, input[0][c + 4], res))
return (0);
c++;
}
return (1);
}
int check_rowr(int cur_row, int r_condition, int *res)
{
int i;
int max;
int count;
i = 3;
max = 0;
count = 0;
while (i >= 0)
{
if (res[cur_row * 4 + i] > max)
{
max = res[cur_row * 4 + i];
count++;
}
i--;
}
if (count != r_condition)
return (0);
return (1);
}
int check_cold(int cur_col, int c_condition, int *res)
{
int i;
int max;
int count;
i = 3;
max = 0;
count = 0;
while (i >= 0)
{
if (res[i * 4 + cur_col] > max)
{
max = res[i * 4 + cur_col];
count++;
}
i--;
}
if (count != c_condition)
return (0);
return (1);
}/* Makefile */
CC = gcc
CFLAGS = -Wall -Wextra -Werror
NAME = rush-01
INCLUDE = -I/.
OBJS = rush-01.o check-table.o check-elem.o
all : $(NAME)
$(OBJS): %.o : %.c
$(CC) $(CFLAGS) -c $(INCLUDE) $^ -o $@
$(NAME) : $(OBJS)
$(CC) $(CFLAGS) $^ -o $@
clean:
rm -f $(OBJS)
fclean: clean
rm -f $(NAME)