반응형
삼성 SW 역량테스트 기출문제인 구슬 탈출 2를 풀어보겠습니다.
문제를 풀기 전 단계별로 생각하는것이 필요합니다.
첫째로 입력 형식입니다.
첫번째 줄의 두 숫자는 판의 크기입니다.
5 5를 입력으로 받았다면 5행 5열
3 7을 입력으로 받았다면 3행 7열
각 행과 열을 뜻합니다.
이는 입력으로 들어올 구슬판이 몇 개인지 지정되어있지 않고, 입력에서 주어지는 값으로 동적 할당하여 세팅을 해야 한다는 것을 의미합니다.
또 거기에 입력되는 종류는 '#', '.' , 'R' , 'B' , 'O'으로 문자가 입력되기 때문에
2차원 문자 배열의 동적 할당이 필요합니다.
int A,B;
scanf("%d %d",&A,&B);
char **arr; //char 더블포인터 선언
arr = (char**)malloc(sizeof(char*)*A); //A칸 동적할당
for (int i=0;i<A;i++){
arr[i] = (char*)malloc(sizeof(char)*B); //B칸 동적할당 후 A에 매치 (A번반복)
}코드를 잠깐 설명하자면
B개의 문자를 저장할 수 있는 char 포인터가 A 개만큼있고 , 그 char 포인터를 가리키는 char 더블 포인터가 하나 있습니다.
그 더블 포인터가 각각의 char 포인터를 가리킵니다.
예를 들면 좌측의 메모리가 char ** 포인터 arr이고 , A칸(포인터를 가리킬 수 있는 사이즈만큼 *A칸)의 메모리를 생성하였습니다.
그리고 이 생성된 arr을 arr [0]~ arr [A]로 각각의 인덱스를 가리킬 수 있으며,
이 각각의 인덱스에 문자 B개를 저장하여 가리킬 수 있는 포인터를 생성하여 가리키게 합니다.
(B칸짜리 문자 포인터 생성 후 그 포인터를 가리키게 함)
이를 각각의 인덱스만큼 반복하여 생성하면 총
(A*B) 칸짜리 메모리를 동적 할당하였고 이를 가리키는 + A 칸짜리 메모리를 동적 할당하였습니다.
이후 마지막에 짝으로 꼭 해줘야 하는 필수과정이 있습니다.
for (int i=0; i<A;i++){
free(arr[i]);
}
free(arr);이는 각각
의 char 포인터를 메모리 반납
이후 char ** 를 반납입니다.
미리 소스 마지막에 추가해두시기 바랍니다.
우선 소스를 하나하나 찢어보기 전에 알고리즘의 큰 틀을 먼저 말씀드리겠습니다.
입력으로 들어온 구슬판이 있을 때 , 그 구슬판의 원본은 유지한 채로 R , B 구슬의 좌표만 움직일 겁니다.
구슬판의 움직임은 총 4가지입니다.
상 , 하 , 좌 , 우로 기울여 구슬이 끝까지 가서 멈출 때까지가 한 동작입니다.
그리고 게임의 상태는 총 3가지로 나뉠 수 있습니다.
한 동작에서 R만 O로 들어가는 경우 <- 이 경우가 게임의 승리입니다.
한 동작에서 B만 O로 들어가는 경우 <- 이 경우는 패배입니다.
한 동작에서 R이 O로 들어갔지만 B도 O로 들어가는 경우 <- 이 경우를 주의해야 합니다 이 경우는 패배 조건인데 승리로 실수할 수 있기 때문입니다. 따라서 R이 구멍을 통해 나온다고 해도 B를 검사해야 합니다.
구슬을 10번 이하로 움직일 수 있는 총경우의 수를 탐색하여 , 그 횟수가 가장 적은 것을 기록하여 출력하는 것이 목표입니다.
최초로 움직일 수 있는 방향은 4방향입니다.
그다음 움직이는 방향부터는 그에 수직 하는 2방향입니다.(이미 움직인 방향으로 움직여도 움직이지 않고 다시 반대방향으로 움직여 돌아온다고 해도 의미가 없음 최소 움직임을 구하는 데에 고려할 필요가 없으니 고려하지 않음)
따라서 4 * 2^9 가 총경우의 수일 것입니다.
그 경우의 수를 R의 좌표 B의 좌표를 정하여 그 좌표를 이동시켜 가면서 상태를 검증하고
최솟값을 찾겠습니다.
int main(){
int A,B;
int bpoint[2], rpoint[2];
scanf("%d %d",&A,&B);
char **arr;
char *temp = (char*)malloc(sizeof(char)*(B+1));
arr = (char**)malloc(sizeof(char*)*A);
for (int i=0;i<A;i++){
arr[i] = (char*)malloc(sizeof(char)*B);
}
for (int i=0;i<A;i++){
scanf("%s",temp);
for (int j = 0; j < B; j++)
{
arr[i][j] = temp[j];
}
}
for (int i=0;i<A;i++){
for (int j=0; j<B;j++){
if(arr[i][j]=='B'){
bpoint[0] = i;
bpoint[1] = j;
}
if(arr[i][j]=='R'){
rpoint[0] = i;
rpoint[1] = j;
}
}
}
printf("%d",checkshort(arr,bpoint,rpoint,0,0));
for (int i=0; i<A;i++){
free(arr[i]);
}
free(arr);
free(temp);
}우선 메인 함수입니다.
구슬판을 입력받은 뒤 B 와 R의 최초 좌표를 기록합니다.
그 뒤 checkshort라는 함수를 실행하여 실제 최솟값을 계산합니다.
int checkshort(char **arr,int Bpoint[] , int Rpoint[], int check,int direction){
int rp[2], bp[2];
int sroot=11,temp;
rp[0] = Rpoint[0];
rp[1] = Rpoint[1];
bp[0] = Bpoint[0];
bp[1] = Bpoint[1];
if (check==0){
temp = checkshort(arr,bp,rp,check+1,1);
if (sroot>temp){
sroot= temp;
}
temp = checkshort(arr,bp,rp,check+1,2);
if (sroot>temp){
sroot= temp;
}
temp = checkshort(arr,bp,rp,check+1,3);
if (sroot>temp){
sroot= temp;
}
temp = checkshort(arr,bp,rp,check+1,4);
if (sroot>temp){
sroot= temp;
}
if(sroot>10){
return -1;
}
else{
return sroot;
}
}
else if(check>10){
return 11;
}
else if (direction==1){
temp = leftcheck(arr,bp,rp);
if (temp==1){
temp = checkshort(arr,bp,rp,check+1,3);
if (sroot>temp){
sroot= temp;
}
temp = checkshort(arr,bp,rp,check+1,4);
if (sroot>temp){
sroot= temp;
}
return sroot;
}
else if (temp ==2){
return 11;
}
else if(temp ==3){
return check;
}
}
else if (direction==2){
temp = rightcheck(arr,bp,rp);
if (temp==1){
temp = checkshort(arr,bp,rp,check+1,3);
if (sroot>temp){
sroot= temp;
}
temp = checkshort(arr,bp,rp,check+1,4);
if (sroot>temp){
sroot= temp;
}
return sroot;
}
else if (temp ==2){
return 11;
}
else if(temp ==3){
return check;
}
}
else if (direction==3){
temp = upcheck(arr,bp,rp);
if (temp==1){
temp = checkshort(arr,bp,rp,check+1,1);
if (sroot>temp){
sroot= temp;
}
temp = checkshort(arr,bp,rp,check+1,2);
if (sroot>temp){
sroot= temp;
}
return sroot;
}
else if (temp ==2){
return 11;
}
else if(temp ==3){
return check;
}
}
else if (direction==4){
temp =downcheck(arr,bp,rp);
if(temp ==1){
temp = checkshort(arr,bp,rp,check+1,1);
if (sroot>temp){
sroot= temp;
}
temp = checkshort(arr,bp,rp,check+1,2);
if (sroot>temp){
sroot= temp;
}
return sroot;
}
else if (temp ==2){
return 11;
}
else if(temp ==3){
return check;
}
}
else{
return 11;
}
}R의 좌표와 B의 좌표 , 그리고 방금 움직인 방향을 받고 , 매 회차 정보를 check로 받아 진행하는 재귀 함수입니다.
direction을 받아 방금 방향과 수직 한 방향을 선택하기 위해 그것을 받고 R , B포인터를 각각 움직여 서 다음 재귀 함수에 넣어주고 (이때 ckeck 는 하나 더해줌) , 재귀함수의 check 가 11이되었을때 즉 10회차를 넘겼을때 종료 또는 게임을 이긴 상태라면 종료가되는 함수입니다.
이 때 매 방향을 체크하여 포인트를 옮겨주고 , 게임이 이겼는지 진행하는 상태인지를 알 여주는 함수는 각
up , down , right , left check함수를 통해 확인합니다.
각 함수는 동일한 원리기 때문에 check함수는 한 개만 해설해드리도록 하겠습니다.
// continue = 1 , fail = 2 , success = 3
// 체크 후 상태값을 3가지로 다룬다.
int leftcheck(char **arr, int Bpoint[],int Rpoint[]){
int condition = 1;
if(Bpoint[1]<Rpoint[1]){
while (1)
{
if (arr[Bpoint[0]][Bpoint[1]-1]=='O'){
return 2;
}
else if (arr[Bpoint[0]][Bpoint[1]-1]=='#'){
break;
}
else if((Bpoint[0]==Rpoint[0])&&((Bpoint[1]-1)==Rpoint[1])){
break;
}
else{
Bpoint[1] = Bpoint[1]-1;
}
}
while (1)
{
if (arr[Rpoint[0]][Rpoint[1]-1]=='O'){
return 3;
}
else if (arr[Rpoint[0]][Rpoint[1]-1]=='#'||((Bpoint[0]==Rpoint[0])&&(Bpoint[1]==(Rpoint[1]-1)))){
return 1;
}
else{
Rpoint[1] = Rpoint[1]-1;
}
}
}
else{
while (1)
{
if (arr[Rpoint[0]][Rpoint[1]-1]=='O'){
condition =3;
Rpoint[1] = Rpoint[1]-1;
break;
}
else if ((arr[Rpoint[0]][Rpoint[1]-1]=='#')||((Bpoint[0]==Rpoint[0])&&(Bpoint[1]==(Rpoint[1]-1)))){
break;
}
else{
Rpoint[1] = Rpoint[1]-1;
}
}
while (1)
{
if (arr[Bpoint[0]][Bpoint[1]-1]=='O'){
return 2;
}
else if ((arr[Bpoint[0]][Bpoint[1]-1]=='#')||((Bpoint[0]==Rpoint[0])&&((Bpoint[1]-1)==Rpoint[1]))){
return condition;
}
else{
Bpoint[1] = Bpoint[1]-1;
}
}
}
}check함수는 int 타입으로 반환 값으로 컨디션을 줍니다.
1번을 리턴 받으면 회차를 진행 2번은 실패 3번은 성공으로 간주합니다.
B포인터와 R포인터가 누가 왼쪽이고 오른쪽인지에 따라 옮기는 순서를 달리합니다.(구슬 두 개가 겹칠 수 없기 때문)
#include<stdio.h>
#include<stdlib.h>
// continue = 1 , fail = 2 , success = 3
// 체크 후 상태값을 3가지로 다룬다.
int leftcheck(char **arr, int Bpoint[],int Rpoint[]){
int condition = 1;
if(Bpoint[1]<Rpoint[1]){
while (1)
{
if (arr[Bpoint[0]][Bpoint[1]-1]=='O'){
return 2;
}
else if (arr[Bpoint[0]][Bpoint[1]-1]=='#'){
break;
}
else if((Bpoint[0]==Rpoint[0])&&((Bpoint[1]-1)==Rpoint[1])){
break;
}
else{
Bpoint[1] = Bpoint[1]-1;
}
}
while (1)
{
if (arr[Rpoint[0]][Rpoint[1]-1]=='O'){
return 3;
}
else if (arr[Rpoint[0]][Rpoint[1]-1]=='#'||((Bpoint[0]==Rpoint[0])&&(Bpoint[1]==(Rpoint[1]-1)))){
return 1;
}
else{
Rpoint[1] = Rpoint[1]-1;
}
}
}
else{
while (1)
{
if (arr[Rpoint[0]][Rpoint[1]-1]=='O'){
condition =3;
Rpoint[1] = Rpoint[1]-1;
break;
}
else if ((arr[Rpoint[0]][Rpoint[1]-1]=='#')||((Bpoint[0]==Rpoint[0])&&(Bpoint[1]==(Rpoint[1]-1)))){
break;
}
else{
Rpoint[1] = Rpoint[1]-1;
}
}
while (1)
{
if (arr[Bpoint[0]][Bpoint[1]-1]=='O'){
return 2;
}
else if ((arr[Bpoint[0]][Bpoint[1]-1]=='#')||((Bpoint[0]==Rpoint[0])&&((Bpoint[1]-1)==Rpoint[1]))){
return condition;
}
else{
Bpoint[1] = Bpoint[1]-1;
}
}
}
}
int rightcheck(char **arr, int Bpoint[],int Rpoint[]){
int condition = 1;
if(Bpoint[1]>Rpoint[1]){
while (1)
{
if (arr[Bpoint[0]][Bpoint[1]+1]=='O'){
return 2;
}
else if (arr[Bpoint[0]][Bpoint[1]+1]=='#'||(Bpoint[0]==Rpoint[0]&&(Bpoint[1]+1)==Rpoint[1])){
break;
}
else{
Bpoint[1] = Bpoint[1]+1;
}
}
while (1)
{
if (arr[Rpoint[0]][Rpoint[1]+1]=='O'){
return 3;
}
else if (arr[Rpoint[0]][Rpoint[1]+1]=='#'||(Bpoint[0]==Rpoint[0]&&Bpoint[1]==(Rpoint[1]+1))){
return 1;
}
else{
Rpoint[1] = Rpoint[1]+1;
}
}
}
else{
while (1)
{
if (arr[Rpoint[0]][Rpoint[1]+1]=='O'){
condition =3;
Rpoint[1] = Rpoint[1]+1;
break;
}
else if (arr[Rpoint[0]][Rpoint[1]+1]=='#'){
break;
}
else if((Bpoint[0]==Rpoint[0]&&(Bpoint[1]==(Rpoint[1]+1)))){
break;
}
else{
Rpoint[1] = Rpoint[1]+1;
}
}
while (1)
{
if (arr[Bpoint[0]][Bpoint[1]+1]=='O'){
return 2;
}
else if (arr[Bpoint[0]][Bpoint[1]+1]=='#'||(Bpoint[0]==Rpoint[0]&&(Bpoint[1]+1)==Rpoint[1])){
return condition;
}
else{
Bpoint[1] = Bpoint[1]+1;
}
}
}
}
int upcheck(char **arr, int Bpoint[],int Rpoint[]){
int condition = 1;
if(Bpoint[0]<Rpoint[0]){
while (1)
{
if (arr[Bpoint[0]-1][Bpoint[1]]=='O'){
return 2;
}
else if (arr[Bpoint[0]-1][Bpoint[1]]=='#'||((Bpoint[0]-1)==Rpoint[0]&&Bpoint[1]==Rpoint[1])){
break;
}
else{
Bpoint[0] = Bpoint[0]-1;
}
}
while (1)
{
if (arr[Rpoint[0]-1][Rpoint[1]]=='O'){
return 3;
}
else if (arr[Rpoint[0]-1][Rpoint[1]]=='#'||(Bpoint[0]==(Rpoint[0]-1)&&Bpoint[1]==Rpoint[1])){
return 1;
}
else{
Rpoint[0] = Rpoint[0]-1;
}
}
}
else{
while (1)
{
if (arr[Rpoint[0]-1][Rpoint[1]]=='O'){
condition =3;
Rpoint[0] = Rpoint[0]-1;
break;
}
else if (arr[Rpoint[0]-1][Rpoint[1]]=='#'||(Bpoint[0]==(Rpoint[0]-1)&&Bpoint[1]==Rpoint[1])){
break;
}
else{
Rpoint[0] = Rpoint[0]-1;
}
}
while (1)
{
if (arr[Bpoint[0]-1][Bpoint[1]]=='O'){
return 2;
}
else if (arr[Bpoint[0]-1][Bpoint[1]]=='#'||((Bpoint[0]-1)==Rpoint[0]&&Bpoint[1]==Rpoint[1])){
return condition;
}
else{
Bpoint[0] = Bpoint[0]-1;
}
}
}
}
int downcheck(char **arr, int Bpoint[],int Rpoint[]){
int condition = 1;
if(Bpoint[0]>Rpoint[0]){
while (1)
{
if (arr[Bpoint[0]+1][Bpoint[1]]=='O'){
return 2;
}
else if (arr[Bpoint[0]+1][Bpoint[1]]=='#'||((Bpoint[0]+1)==Rpoint[0]&&Bpoint[1]==Rpoint[1])){
break;
}
else{
Bpoint[0] = Bpoint[0]+1;
}
}
while (1)
{
if (arr[Rpoint[0]+1][Rpoint[1]]=='O'){
return 3;
}
else if (arr[Rpoint[0]+1][Rpoint[1]]=='#'||(Bpoint[0]==(Rpoint[0]+1)&&Bpoint[1]==Rpoint[1])){
return 1;
}
else{
Rpoint[0] = Rpoint[0]+1;
}
}
}
else{
while (1)
{
if (arr[Rpoint[0]+1][Rpoint[1]]=='O'){
condition =3;
Rpoint[0] = Rpoint[0]+1;
break;
}
else if (arr[Rpoint[0]+1][Rpoint[1]]=='#'||(Bpoint[0]==(Rpoint[0]+1)&&Bpoint[1]==Rpoint[1])){
break;
}
else{
Rpoint[0] = Rpoint[0]+1;
}
}
while (1)
{
if (arr[Bpoint[0]+1][Bpoint[1]]=='O'){
return 2;
}
else if (arr[Bpoint[0]+1][Bpoint[1]]=='#'||((Bpoint[0]+1)==Rpoint[0]&&Bpoint[1]==Rpoint[1])){
return condition;
}
else{
Bpoint[0] = Bpoint[0]+1;
}
}
}
}
//0 = start , 1= left , 2 = right ,3 = up , 4 = down (direction 의 상태값)
int checkshort(char **arr,int Bpoint[] , int Rpoint[], int check,int direction){
int rp[2], bp[2];
int sroot=11,temp;
rp[0] = Rpoint[0];
rp[1] = Rpoint[1];
bp[0] = Bpoint[0];
bp[1] = Bpoint[1];
if (check==0){
temp = checkshort(arr,bp,rp,check+1,1);
if (sroot>temp){
sroot= temp;
}
temp = checkshort(arr,bp,rp,check+1,2);
if (sroot>temp){
sroot= temp;
}
temp = checkshort(arr,bp,rp,check+1,3);
if (sroot>temp){
sroot= temp;
}
temp = checkshort(arr,bp,rp,check+1,4);
if (sroot>temp){
sroot= temp;
}
if(sroot>10){
return -1;
}
else{
return sroot;
}
}
else if(check>10){
return 11;
}
else if (direction==1){
temp = leftcheck(arr,bp,rp);
if (temp==1){
temp = checkshort(arr,bp,rp,check+1,3);
if (sroot>temp){
sroot= temp;
}
temp = checkshort(arr,bp,rp,check+1,4);
if (sroot>temp){
sroot= temp;
}
return sroot;
}
else if (temp ==2){
return 11;
}
else if(temp ==3){
return check;
}
}
else if (direction==2){
temp = rightcheck(arr,bp,rp);
if (temp==1){
temp = checkshort(arr,bp,rp,check+1,3);
if (sroot>temp){
sroot= temp;
}
temp = checkshort(arr,bp,rp,check+1,4);
if (sroot>temp){
sroot= temp;
}
return sroot;
}
else if (temp ==2){
return 11;
}
else if(temp ==3){
return check;
}
}
else if (direction==3){
temp = upcheck(arr,bp,rp);
if (temp==1){
temp = checkshort(arr,bp,rp,check+1,1);
if (sroot>temp){
sroot= temp;
}
temp = checkshort(arr,bp,rp,check+1,2);
if (sroot>temp){
sroot= temp;
}
return sroot;
}
else if (temp ==2){
return 11;
}
else if(temp ==3){
return check;
}
}
else if (direction==4){
temp =downcheck(arr,bp,rp);
if(temp ==1){
temp = checkshort(arr,bp,rp,check+1,1);
if (sroot>temp){
sroot= temp;
}
temp = checkshort(arr,bp,rp,check+1,2);
if (sroot>temp){
sroot= temp;
}
return sroot;
}
else if (temp ==2){
return 11;
}
else if(temp ==3){
return check;
}
}
else{
return 11;
}
}
int main(){
int A,B;
int bpoint[2], rpoint[2];
scanf("%d %d",&A,&B);
char **arr;
char *temp = (char*)malloc(sizeof(char)*(B+1));
arr = (char**)malloc(sizeof(char*)*A);
for (int i=0;i<A;i++){
arr[i] = (char*)malloc(sizeof(char)*B);
}
for (int i=0;i<A;i++){
scanf("%s",temp);
for (int j = 0; j < B; j++)
{
arr[i][j] = temp[j];
}
}
for (int i=0;i<A;i++){
for (int j=0; j<B;j++){
if(arr[i][j]=='B'){
bpoint[0] = i;
bpoint[1] = j;
}
if(arr[i][j]=='R'){
rpoint[0] = i;
rpoint[1] = j;
}
}
}
printf("%d",checkshort(arr,bpoint,rpoint,0,0));
for (int i=0; i<A;i++){
free(arr[i]);
}
free(arr);
free(temp);
}
질문 있으시면 편하게 남겨주세요
반응형
'코딩 - > 백준 알고리즘 해설' 카테고리의 다른 글
| 백준 삼성 SW 역량 테스트 기출 문제 문제풀이 / 연구소(백준 14502번) (0) | 2021.07.12 |
|---|---|
| 백준 삼성 SW 역량 테스트 기출 문제 문제풀이 / 2048 (Easy) (백준 12100번) (0) | 2021.07.12 |
| 백준 알고리즘 단계별 문제풀이 4 . while문 , A+B - 5 (백준 10952번) (0) | 2021.07.08 |
| 백준 알고리즘 단계별 문제풀이 3 . for문 , X보다 작은 수 (백준 10871번) (1) | 2021.07.06 |
| 백준 알고리즘 단계별 문제풀이 3 . for문 , 별 찍기 - 2 (백준 2439번) (0) | 2021.07.06 |
