아영
- 코드
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
static Map<Integer, List<Integer>> map;
static int K,N;
static int finalStart;
static int[] answer;
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
K = Integer.parseInt(st.nextToken());
N = Integer.parseInt(st.nextToken());
int F = Integer.parseInt(st.nextToken());
answer = new int[N];
map = new HashMap<>();
boolean[] check = new boolean[N];
for (int i = 0; i < F; i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
if(map.containsKey(a)){
List<Integer> friends = map.get(a);
friends.add(b);
friends.stream().sorted();
map.put(a,friends);
}else{
List<Integer> friends = new ArrayList<>();
friends.add(b);
map.put(a,friends);
}
}
for (int n = 1; n < N+1; n++) {
answer[0]=n;
dfs(1,n,new boolean[N+1],answer,false);
if(answer[K-1]!=0) break;
}
Arrays.sort(answer);
for (int i = 0; i < K; i++) {
System.out.println(answer[i]);
}
}
private static void dfs(int idx,int now,boolean[] checked,int[] result,boolean flag){
if(flag) return;
if(idx==K){
answer = Arrays.copyOf(result,K);
flag = true;
return;
}
if(map.containsKey(now)){
List<Integer> friends = map.get(now);
for (int i = 0; i < friends.size(); i++) {
int b = friends.get(i);
if(checked[b]) continue;
checked[b] = true;
result[idx]=b;
dfs(idx+1,b,checked,result,flag);
checked[b] = false;
}
}
}
}
- 시간,메모리
은영
- 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
static int K,N,F;
static int[] answer,friend;
static boolean visit[][];
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine()+" ");
K = Integer.parseInt(st.nextToken());
N = Integer.parseInt(st.nextToken());
F = Integer.parseInt(st.nextToken());
answer = new int [K];
visit = new boolean[N+1][N+1];
Arrays.fill(visit[0], true);
friend = new int[N+1];
friend[0]=N;
for (int i = 0; i < F; i++) {
st = new StringTokenizer(br.readLine()+" ");
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
visit[a][b] = true;
visit[b][a] = true;
friend[a]++;
friend[b]++;
}
if(func(0,0)) {
for (int i = 0; i < K; i++) {
System.out.println(answer[i]);
}
}
else {
System.out.println(-1);
}
}
private static boolean func(int start, int cnt) {
if(cnt==K) {
return true;
}
if(friend[start]<K-cnt) {
return false;
}
for (int i = 1; i <=N; i++) {
if(visit[start][i]) {
boolean isFriend=true;
for (int j = 0; j < cnt; j++) {
if(!visit[answer[j]][i]) {
isFriend=false;
break;
}
}
if(isFriend) {
answer[cnt]=i;
if(func(i,cnt+1))return true;
}
}
}
return false;
}
}
- 시간,메모리
건
- 코드
package day_0524;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class BOJ2026 {
static int n, k;
static boolean[][] relation;
static int[] friendsNum;
static int[] isSelected;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer stk = new StringTokenizer(br.readLine());
k = Integer.parseInt(stk.nextToken());
n = Integer.parseInt(stk.nextToken());
int f = Integer.parseInt(stk.nextToken());
int input1, input2;
relation = new boolean[n][n];
friendsNum = new int[n];
for (int i = 0; i < f; i++) {
stk = new StringTokenizer(br.readLine());
input1 = Integer.parseInt(stk.nextToken()) - 1;
input2 = Integer.parseInt(stk.nextToken()) - 1;
relation[input1][input2] = true;
relation[input2][input1] = true;
friendsNum[input1]++;
friendsNum[input2]++;
}
isSelected = new int[k];
comb(0,0);
System.out.println(-1);
}
static void comb(int cnt, int start) {
if(cnt == k) {
for (int i = 0; i < k; i++) {
System.out.println(isSelected[i] + 1);
}
System.exit(0);
}
for (int i = start; i < n; i++) {
if (cnt == 0) {
if (friendsNum[i] >= k - 1) {
isSelected[cnt] = i;
comb(cnt + 1, start + 1);
}
} else {
for (int j = 0; j < cnt; j++) {
if (!relation[isSelected[j]][i]) {
break;
}
if (j == cnt - 1) {
isSelected[cnt] = i;
comb(cnt + 1, start + 1);
}
}
}
}
}
}
- 시간,메모리
용문
- 코드
class BJ2026 {
private var K = 0
private var N = 0
private var F = 0
private var selected: [Bool] = []
private var friends: [Int : Set<Int>] = [ : ]
private var answer: [Int] = []
private var picnicFriends: [Int] = []
private var done = false
func solve() {
readComponents()
calc()
printAnswer()
}
private func readComponents() {
let temp = readLine()!.split(separator: " ").map { Int($0)! }
self.K = temp[0]
self.N = temp[1]
self.F = temp[2]
self.selected = .init(repeating: false, count: N + 1)
for _ in 0..<F {
let duo = readLine()!.split(separator: " ").map { Int($0)! }
let first = duo[0]
let second = duo[1]
if var firstFriends = friends[first] {
firstFriends.insert(second)
friends[first] = firstFriends
} else {
var tf = Set<Int>()
tf.insert(second)
friends[first] = tf
}
if var secondFriends = friends[second] {
secondFriends.insert(first)
friends[second] = secondFriends
} else {
var ts = Set<Int>()
ts.insert(first)
friends[second] = ts
}
}
}
private func calc(count: Int = 0) {
if done { return }
if count == K {
answer = picnicFriends
done = true
return
}
for index in 1...N {
if selected[index] || friends[index]?.count ?? 0 < K - 1 { continue }
var flag = true
for friend in picnicFriends {
if let friendship = friends[friend], !friendship.contains(index) { flag = false }
}
if flag {
selected[index] = true
picnicFriends.append(index)
calc(count: count + 1)
selected[index] = false
picnicFriends.removeLast()
}
}
}
private func printAnswer() {
if answer.isEmpty {
print(-1)
} else {
for value in answer {
print(value)
}
}
}
}
BJ2026().solve()
- 시간,메모리
