이번주 알고리즘 스터디 풀어야 할 두 문제 중에 이거 한 문제밖에 못 풀었다 😢 그래도 아직 익숙하지 않은 c 로 풀어보려고 노력했다 👏 !
문제
알고리즘 종류 ) 구현 알고리즘
test case 1
input :
4 4
1 1 0
1 1 1 1
1 0 0 1
1 1 0 1
1 1 1 1
output :
3
풀이 & 코드
딱 c 초보자가 작성했을 법한 코드이다 ! 포인터를 최대한 써보려고 했는데 딱히 포인터를 쓸 곳이 없었던 것 같다 (아닐 수도 ..?!)
전역변수 선언 (이라고 쓰지만 그냥 생각나는 애들 우선 다 선언해주었다)
# include <stdio.h>
int cur[3];
int nn_cur[3];
int n,m;
int move(int a[3]);
main 함수 첫번째 부분 -> input 값 받아서 저장하기
int main(){
int x,N,W,D;
scanf("%d %d\n",&n,&m);
scanf("%d %d %d\n",&N,&W,&D);
cur[0]=W;
cur[1]=N;
cur[2]=D;
int map[n][m];
for (int i=0;i<n;i++)
{
int o,t,th,f;
scanf("%d %d %d %d",&o,&t,&th,&f);
int put[4]={ o,t,th,f };
for (int j=0;j<m;j++){
map[i][j]=put[j];
}
} //여기까지 자료 넣기 끝!
초기화
int count=1;
int cycle=0;
count 를 통해 몇 번 이동했는지를 세어줄 것이고, cycle 을 통해서 해당 위치 반시계방향 순으로 동서남북 주변을 현재 얼만큼 이동 시도했는지 세어줄 것이다 (동서남북 다 못 가면 차선책인 뒤로 가기를 해야하므로), nn_cur 에는 각 방향으로 이동을 시도할 좌표를 넣어주려고 한다(사실 이 부분은 좀 어거지로 작성한 것 같다)
반복문 시작 !
- move 함수 정의
int move(int a[3]){
//printf("%d",*);
int original[3];
original[0]=a[0];
original[1]=a[1];
original[2]=a[2];
if (a[2]==0 && 0<=a[0]-1)
a[0]=a[0]-1;
else if (a[2]==1 && a[1]+1<n)
a[1]=a[1]+1;
else if (a[2]==2 && a[0]+1<n)
a[0]=a[0]+1;
else if (a[2]==3 && 0<=a[1]-1)
a[1]=a[1]-1;
nn_cur[0]=a[0];
nn_cur[1]=a[1];
nn_cur[2]=a[2];
cur[0]=original[0];
cur[1]=original[1];
cur[2]=original[2];
return 0;
}
북 : 0 / 동 : 1 / 남 : 2 / 서 : 3
이므로 현재 북쪽을 바라보고 있다면 0 - > 3으로 바꿔야한다 ! (반시계방향으로 움직이므로 )
move 를 통해 새로 이동을 시도할 좌표 nn_cur 이 갱신되고, 원래 좌표는 cur 에서 유지된다.
while (1)
{
if (cur[2]==0)
{cur[2]=3;
move(cur);}
else
{
cur[2]=cur[2]-1;
move(cur);}
바다가 아니고 방문한 곳이 아니라면
if (map[nn_cur[0]][nn_cur[1]] !=1) //바다가 아니고, 방문한 곳이 아니라면 !
{count+=1;
map[cur[0]][cur[1]]=1; //현재 위치는 방문
for (int x=0;x<3;x++)
cur[x]=nn_cur[x];
cycle=0;}
바다가 아니고 방문한 곳이 아니라면, 해당 위치로 이동해야 된다 ! 현재 머물고 있는 위치는 따라서 이미 방문한 곳이 되도록 1로 변경해주고 새로 이동할 위치에서 반시계방향 순으로 동서남북 주변을 다시 탐색해야하므로 cycle 도 갱신해준다
바다이거나 이미 방문한 곳이라면
else
{
cycle+=1;
int ori=cur[2];
동서남북 네 방향을 모두 탐색했는데 갈 곳이 없다면 차선책인 뒤로 가기를 해야한다. 현재 차선책까지 얼마나 남았는지를 갱신하기 위해 cycle 을 증가시킨다. 이후 뒤로 가기를 하게 될 경우, 바라보는 방향을 유지한 채 가야하기 때문에 미리 어디 쪽을 바라봤는지 기록해준다.
동서남북 어느 곳도 갈 수가 없다면
동서남북 어느 곳도 갈 수 없다면 뒤로 가기를 해야한다.
현재 북 쪽을 바라본다면, 그 방향 그대로 뒤로 가기 하면 남쪽으로 이동한다.
남쪽을 바라본다면, 그 방향 그대로 뒤로 가기 하면 북쪽으로 이동한다.
동쪽을 바라보고 있다면, 그 방향 그대로 뒤로 가기 하면 서쪽으로 이동한다.
서쪽을 바라보고 있다면, 그 방향 그대로 뒤로 가기 하면 동쪽으로 이동한다.
if (cycle==4)
{ if (ori==0)
cur[2]=2;
else if (ori==1)
cur[2]=3;
else if (ori==2)
cur[2]=0;
else
cur[2]=1;
move(cur);
nn_cur[2]=ori;
만약 뒤로 이동하려고 하는 방향도 0이 아닐 경우 (;바다이거나 이미 방문한 장소) break 하고 게임을 종료시켜야한다
if (map[nn_cur[0]][nn_cur[1]] !=0)
{printf("정답은 %d!\n",count);
break;}
뒤로 이동하려는 곳은 아직 방문할 수 있는 곳일 경우, 뒤로 이동하면 된다.
else
{for (int x=0;x<3;x++)
cur[x]=nn_cur[x];
cycle=0;
}
} //뒤로 감 !
전체 코드
# include <stdio.h>
int cur[3];
int nn_cur[3];
int n,m;
int move(int a[3]);
int main(){
int x,N,W,D;
scanf("%d %d\n",&n,&m);
scanf("%d %d %d\n",&N,&W,&D);
cur[0]=W;
cur[1]=N;
cur[2]=D;
int map[n][m];
for (int i=0;i<n;i++)
{
int o,t,th,f;
scanf("%d %d %d %d",&o,&t,&th,&f);
int put[4]={ o,t,th,f };
for (int j=0;j<m;j++){
map[i][j]=put[j];
}
} //여기까지 자료 넣기 끝!
int count=1;
int cycle=0;
int n_cur[3];
while (1)
{
if (cur[2]==0)
{
cur[2]=3;
move(cur);}
else
{
cur[2]=cur[2]-1;;
move(cur);}
if (map[nn_cur[0]][nn_cur[1]] !=1) //바다가 아니고, 방문한 곳이 아니라면 !
{count+=1;
map[cur[0]][cur[1]]=1;
for (int x=0;x<3;x++)
cur[x]=nn_cur[x];
cycle=0;}
else
{
cycle+=1;
int ori=cur[2];
if (cycle==4)
{ if (ori==0)
cur[2]=2;
else if (ori==1)
cur[2]=3;
else if (ori==2)
cur[2]=0;
else
cur[2]=1;
move(cur);
nn_cur[2]=ori;
if (map[nn_cur[0]][nn_cur[1]] !=0)
{printf("정답은 %d!\n",count);
break;}
else
{for (int x=0;x<3;x++)
cur[x]=nn_cur[x];
cycle=0;
}
} //뒤로 감 !
}
}
return 0;
}
int move(int a[3]){
//printf("%d",*);
int original[3];
original[0]=a[0];
original[1]=a[1];
original[2]=a[2];
if (a[2]==0 && 0<=a[0]-1)
a[0]=a[0]-1;
else if (a[2]==1 && a[1]+1<n)
a[1]=a[1]+1;
else if (a[2]==2 && a[0]+1<n)
a[0]=a[0]+1;
else if (a[2]==3 && 0<=a[1]-1)
a[1]=a[1]-1;
nn_cur[0]=a[0];
nn_cur[1]=a[1];
nn_cur[2]=a[2];
cur[0]=original[0];
cur[1]=original[1];
cur[2]=original[2];
return 0;
}