1459: 숫자고르기

정올.문제

코드 숫자고르기.c

#include <stdio.h>
 //Compiler version gcc 6.3.0
 
 
 int num[111], val[111], visit[111];
 int answer;
 
 void roop(int N)
 {
     int i =0;
     
     for(i = 1; i <= N; i++)
         scanf("%d ", &num[i]);
}
 
//k == instans check == 비교값
 void REC(int k, int check)
 {
     //Nok 탈출 조건 ex) 3 -> 4 -> 1 -> 4의 경우 4는 이미 방문한 곳으로 Reuturn
    //탈출을 안하면 4 -> 1 -> 4 ->1 ... 무한반복
     if(visit[k] == 1) 
         return; // visit check 전으로 visit 해제안하고 return
     
     visit[k] = 1;
     
     if(check == num[k]) //정답인 경우 저장
     {
         answer++;
         val[answer] = check;
     }
     
     else
         REC(num[k], check);
     
     visit[k] = 0;
     return;
 }
 
 int main(void)
 {
   int inputN = 0;
   int max = 0, i = 0;
 
   scanf("%d ", &inputN);
   max = inputN; //#define으로 가능하나 에러발생으로 변수화 시킴
   
     roop(inputN); // 초기 input data를 입력 받음.
     
     for(i = 1; i<= max; i++) //inputN == 총 갯수 == MAX
         REC(num[i], i); // 시작 값과 비교할 값  && 시작 값은 지속 적인 변동 && 비교할 값은 고정 된 값
     
     /* 정답 */
     printf("%d\n", answer);
     for(i = 1; i<= answer; i++)
         printf("%d\n", val[i]);
 
    return 0;
 } //eof main

해설(?)

아래 표를 예시로 위에 첫줄(1,2,3,4,5,6,7)은 'A'  두번째줄(3,1,1,5,5,4,6)은 'B'일때

A라인은 항상 고정됨으로 1부터 시작하여 N까지로 고정되며

B라인은 항상 input data로 주어진다.

코드에서는 'NUM'이라고 선언한 배열을 이용한다.

NUM[ i ]에서 i는  A라인을 나타내며

Sequence 1)
K 1  check 1 num[1] 3   첫번째 ( if (visit[k] == 1) == fasle   visit[1] = 1      두번째 if(1 == 3)으로 REC 재진입
Sequence 2)
K 3 check 1 num[3] 1   첫번째 (if(visit[3] == 1) == fasle   visit[3] = 1   두번째 if(1 == 1)    answer는 0으로 시작으로 answer++    val[1] = 1
Sequence 3)
else문은 pass     visit [3]  = 0   return 후   visit[1] = 0

마무리하며.

문제 풀이에 대한 느낌은 Visited의 대한 이해가 필요하다.

방문했던 곳과 다시 나오면서 방문한 흔적을 지우는 과정의 이해가 핵심이라고 생각한다.