• 카테고리

    질문 & 답변
  • 세부 분야

    알고리즘 · 자료구조

  • 해결 여부

    미해결

코드 질문입니다.

21.08.28 16:13 작성 조회수 162

0

중복순열문제 질문이 있습니다.
저는 중복수열 문제를 BFS 로 풀었습니다. 혹시 이렇게 풀면 문제가 될까요??
채점 기능이 없어 질문과 코드 올립니다.
감사합니다. 좋은 하루 되십시오.
public class Main {
	
	static int n;
	static int m;
	static Queue<String> Q;
	
	public void BFS(String str) {
		Q = new LinkedList<>();
		Q.offer(str);
		int L = 0;
		
		while(!Q.isEmpty()) {
			int len = Q.size();
			for(int i=0; i<len; i++) {
				String tmp = Q.poll();
				for(int j=1; j<=n; j++) {
					if(tmp == "0") Q.offer(String.valueOf(j));
					else Q.offer(tmp+" "+String.valueOf(j));
				}
			}
			L++;
			if(L==m) return;
		}
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		n = kb.nextInt();
		m = kb.nextInt();
		
		T.BFS("0");
		for(String x:Q) {
			System.out.println(x);
		}
	}
}

답변 1

답변을 작성해보세요.

0

안녕하세요^^

중복순열을 DFS로 하는 것은 차우에 있을 순열을 배우기 위한 사전작업의 성격입니다. 그리고 어떤 경우의 수들을 따질때는 DFS를 사용하시고, 최단거리, 최소거리를 구할 때는 BFS라는 사실을 염두에 두고 알고리즘 공부를 하면 나중 코딩테스트 실전문제에 도움이 될 겁니다.