백준 2422번
https://www.acmicpc.net/problem/2422

문제

---

한윤정과 친구들은 이탈리아로 방학 여행을 갔다. 이탈리아는 덥다. 윤정이와 친구들은 아이스크림을 사먹기로 했다. 아이스크림 가게에는 N종류의 아이스크림이 있다. 모든 아이스크림은 1부터 N까지 번호가 매겨져있다. 어떤 종류의 아이스크림을 함께먹으면, 맛이 아주 형편없어진다. 따라서 윤정이는 이러한 경우를 피하면서 아이스크림을 3가지 선택하려고 한다. 이때, 선택하는 방법이 몇 가지인지 구하려고 한다.

생각하기

---

• 백트래킹을 사용한다.
  • 백트래킹은 숫자의 모든 조합을 만들 수 있다.
  • 아이스크림의 조합을 찾으라는 부분 부터 백트래킹을 떠올렸다.

• 모든 조합을 만들어보고, 피해야하는 조합을 검사하며 거르는 방식으로 선택했다.

동작

		for(int i=0; i<M; i++) {
			st = new StringTokenizer(br.readLine());
			int num = Integer.parseInt(st.nextToken());
			int num2 = Integer.parseInt(st.nextToken());
			
			comb[num][num2] = true;
			comb[num2][num] = true;
		}	

피해야 하는 조합을 파악하기 위해서 미리 boolean형 comb 2차원 배열을 만들어뒀다.

입력받는 조합의 값을 인덱스로 받아서 comb배열에 true값으로 저장하면 된다.

이렇게 하면 나중에 백트래킹을 통한 탐색으로 만들어진 조합을 다시 인덱스 값으로 넣어서 해당 조합의 값이 true인지 아닌지만 검사하면 된다.

        if(depth == 3) {
			for(int i=0; i<3; i++) {
				for(int j=0; j<3; j++) {
					if(comb[ans[i]][ans[j]]) {
						return;
					}
				}
			}
			
			result++;
			return;
		}

재귀 탈출조건인 depth가 3일 경우,

ans배열을 인덱스 값으로 사용하여 comb배열을 탐색한다.
한번이라도 true가 생기면 피해야하는 조합이므로 곧바로 return 한다.

피하지 않아도 되는 조합일 경우, result를 증가시킨다.

코드

---

Java

import java.util.*;
import java.io.*;

public class Main {
	static int N, M;
	static boolean comb[][];
	static int arr[];
	static boolean visit[];
	
	static int ans[];
	static int result = 0;
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		arr = new int[N+1];
		visit = new boolean[N+1];
		
		comb = new boolean[N+1][N+1]; // 조합을 담는 배열
		ans = new int[3]; // 백트래킹 정답 담는 배열
		
		for(int i=1; i<=N; i++) arr[i-1] = i;
		
		for(int i=0; i<M; i++) {
			st = new StringTokenizer(br.readLine());
			int num = Integer.parseInt(st.nextToken());
			int num2 = Integer.parseInt(st.nextToken());
			
			comb[num][num2] = true;
			comb[num2][num] = true;
		}		

		DFS(0, 0);
		
		System.out.println(result);
	} // End of main
	
	private static void DFS(int idx, int depth) { // 백트래킹
		
        if(depth == 3) {
			for(int i=0; i<3; i++) {
				for(int j=0; j<3; j++) {
					if(comb[ans[i]][ans[j]]) {
						return;
					}
				}
			}
			
			result++;
			return;
		}
		
		for(int i=idx; i<N; i++) {
			if(visit[i]) continue;
			visit[i] = true;
			ans[depth] = arr[i];
			DFS(i+1, depth+1);
			visit[i] = false;
		}
		
	} // End of DFS
} // End of Main class

Kotlin

import java.util.*
import java.io.*

private var N = 0; private var M = 0
private lateinit var arr : IntArray
private lateinit var visit : BooleanArray
private lateinit var comb : Array<BooleanArray>
private lateinit var ans : IntArray

private var result = 0

fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    var st = StringTokenizer(br.readLine())
    N = st.nextToken().toInt(); M = st.nextToken().toInt()
    arr = IntArray(N+1)
    visit = BooleanArray(N+1)
    comb = Array(N+1){ BooleanArray(N+1) }
    ans = IntArray(3)

    for(i in 1..N) arr[i-1] = i

    for(i in 0 until M) {
        st = StringTokenizer(br.readLine())
        var x = st.nextToken().toInt()
        var y = st.nextToken().toInt()
        comb[x][y] = true; comb[y][x] = true
    }

    DFS(0, 0);

    print(result)
} // End of main

private fun DFS(index : Int, depth : Int) {
    if(depth == 3) {
        for(i in 0 until 3) {
            for(j in 0 until 3) {
                if(comb[ans[i]][ans[j]]) return
            }
        }

        result++
        return
    }

    for(i in index until N) {
        if(visit[i]) continue;

        visit[i] = true
        ans[depth] = arr[i]
        DFS(i+1, depth+1)
        visit[i] = false
    }
} // End of DFS