[BOJ] 5568 카드 놓기

🔗 Problem

https://www.acmicpc.net/problem/5568

👩‍💻 Code

package baekjoon;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.io.IOException;

// 카드 놓기

public class BJ5568 {
	
	static int n;
	static int k;
	static String[] arr;
	static boolean[] visited;
	static HashSet<String> set = new HashSet<>();
	static StringBuilder sb;
	
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());
		k = Integer.parseInt(br.readLine());
		arr = new String[n];
		visited = new boolean[n];
		
		for(int i = 0; i < n; i++) {
			arr[i] = br.readLine();
		}
		
		dfs(0, 0);
		System.out.println(set.size());
	
	}
	
	private static void dfs(int level, int idx) {
		
		if(level == k) {
			String number = sb.toString();
			if(!set.contains(number)) set.add(number);
			return;
		}
		
		if(level == 0) sb = new StringBuilder();
		
		for(int i = 0; i < n; i++) {
			if(level != 0 && i == idx) continue;
			if(!visited[i]) {
				visited[i] = true;
				sb.append(arr[i]);
				dfs(level + 1, i);
				visited[i] = false;
				
                int start = sb.length() - arr[i].length();
				sb.delete(start, sb.length());
			}
		}
	}

}

💡 Learned

아이디어

  • Level이 0일 때, 즉 아직 카드를 고르지 않았을 때 StringBuilder를 생성하고
    sb에 고른 카드를 담도록 하였다.
  • 이후 해당 노드 탐색을 종료하면 sb에 담은 카드를 삭제해 주었다.

좋은 웹페이지 즐겨찾기