[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
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());
}
}
}
}
아이디어
- Level이 0일 때, 즉 아직 카드를 고르지 않았을 때 StringBuilder를 생성하고
sb에 고른 카드를 담도록 하였다. - 이후 해당 노드 탐색을 종료하면 sb에 담은 카드를 삭제해 주었다.
Author And Source
이 문제에 관하여([BOJ] 5568 카드 놓기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@ssoyeong/BOJ-5568-카드-놓기저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)