자바 알고리즘 문제 풀이 입문. ch08. DFS, BFS 활용 : 중복순열 구하기

 

https://hyejin.tistory.com/1277

자바 알고리즘 문제 풀이 입문. ch08. DFS, BFS 활용 : 최대점수 구하기 DFS

-> 이전 문제 풀이 

 

 

 

4. 중복순열 구하기 

설명

1부터 N까지 번호가 적힌 구슬이 있습니다.

이 중 중복을 허락하여 M번을 뽑아 일렬로 나열 하는 방법을 모두 출력합니다.

 

입력 설명

첫 번째 줄에 자연수 N(3<=N<=10)과 M(2<=M<=N) 이 주어집니다.

 

출력 설명

첫 번째 줄에 결과를 출력합니다.

출력순서는 사전순으로 오름차순으로 출력합니다.

 

입력 예제 1

3 2 

 

출력 예제 1

1 1

1 2

1 3

2 1

2 2

2 3

3 1

3 2

3 3

 

 

문제 풀이 1

public class FindingDuplicatePermutations
{
   static int n,m;
   
   public void DFS(int val)
   {
      if (val > n) {
         return;
      }else {
         for (int i = 1; i <= n; i++)
         {
            System.out.println(val + " " + i);
         }
         DFS(val + 1);
      }
   }
   
   public static void main(String[] args)
   {
      FindingDuplicatePermutations findingDuplicatePermutations = new FindingDuplicatePermutations();
      Scanner scanner = new Scanner(System.in);
      n = scanner.nextInt();
      m = scanner.nextInt();
      
      findingDuplicatePermutations.DFS(1);
   }
}

👩‍💻 -> 씁.. ㅋㅋ 이렇게 풀면 안된다,,, 2번 뽑을때는 출력 예제에 맞게 출력되겠지만 3번 뽑을 때부터는 출력 예제에 맞게 안된다..!!!! 바보 아닌가 싶네.. ㅎ 

 

 

문제 풀이 2

static int[] pm;
static int n, m;

public void DFS(int L)
{
   if (L == m) {
      for (int i : pm)
      {
         System.out.print(i + " ");
      }
         System.out.println();
   }else {
      for (int i = 1; i <= n; i ++ )
      {
         pm[L] = i;
         DFS(L + 1);
      }
   }
}

👾 : 강사님 풀이인데 우선 pm 이라는 배열 하나를 선언해서 풀어야 한다. 

pm[L] = i; 이렇게 선언을 해주고, DFS(L+1) 을 재귀 함수로 호출하면서 답을 구해야 한다. 

처음에는 나도 이해가 안돼서 직접 그림을 그려서 해보니까 이해가 됐다. 

 

말로 풀어보자면... 

DFS(0) 에서 시작을 하는데 if 에서 0이 m 이 아니기 때문에 바로 else 문으로 넘어간다.

else 문에서 for문을 들어오는데 i = 1 에서 pm[0] = 1; 을 넣어주고, DFS(1) 을 호출한다. 

DFS(1) 에서 else 문으로 바로 넘어와 i = 1에서 pm[1]  = 1; 을 넣어주고, DFS(2) 을 호출한다. 

DFS(2)는 L == m에 해당하므로 pm[0], pm[1] 을 출력하고 종료한다.  -> 1 1 

 

다시 DFS(1) 의 i = 2 로 넘어와서 pm[1] = 2; 을 넣어주고, 다시 DFS(2)을 호출한다. 

DFS(2)는 L == m에 해당하므로 pm[0], pm[1] 을 출력하고 종료한다. -> 1 2 

 

DFS(1)의 i = 3으로 넘어와서 pm[1] =3; 을 넣어주고, DFS(2) 을 호출한다.

DFS(2)는 L == m에 해당하므로  pm[0], pm[1] 을 출력하고 종료한다. -> 1 3  

 

DFS(0), i=2 로 넘어와서 pm[0] = 2 를 넣어주고 DFS(1) 를 호출한다. 

DFS(1) i = 1, pm[1] = 1 넣어주고 DFS(2) 를 호출한다. 

DFS(2) 는 L == m에 해당하므로  pm[0], pm[1] 을 출력하고 종료한다. -> 2 1 

 

... 이렇게 반복해주면 된다.