<stdio.han>

[문제 링크]

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

[난이도]

- Gold 4

[알고리즘]

- BFS

- 백트래킹

[코드]

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

public class Main {
    static int N, M, result = 0;
    static int[][] map;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        map = new int[N][M];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        backTracking(0);
        System.out.println(result);
    }

    static void backTracking(int depth) {
        if (depth == 3) {
            result = Math.max(result, checkSafeArea(bfs()));
            return;
        }
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (map[i][j] == 0) {
                    map[i][j] = 1; // 벽을세움
                    backTracking(depth + 1);
                    map[i][j] = 0; // 벽을 되돌려놓음
                }
            }
        }
    }
    static int[][] bfs() {
        int[][] newMap = new int[N][M];
        for (int i = 0; i < N; i++) {
            System.arraycopy(map[i], 0, newMap[i], 0, M);
        }
        Queue<int[]> queue = new LinkedList<>();
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (newMap[i][j] == 2) {
                    queue.add(new int[]{i, j});
                }
            }
        }

        while (!queue.isEmpty()) {
            int[] tmp = queue.poll();
            int x = tmp[0];
            int y = tmp[1];
            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                if (nx >= 0 && nx < N && ny >= 0 && ny < M) {
                    if (newMap[nx][ny] == 0) {
                        newMap[nx][ny] = 2;
                        queue.add(new int[]{nx, ny});
                    }
                }
            }
        }
        return newMap;
    }
    static int checkSafeArea(int[][] newMap) {
        int safeArea = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (newMap[i][j] == 0) {
                    safeArea++;
                }
            }
        }
        return safeArea;
    }
}

[풀이]

4방탐색을하며 바이러스를 퍼트리는 부분은 일반적인 bfs알고리즘을 활용해 푼다. 더 생각해야할 부분은 벽을 3개 세우는데 반드시 3개를 세워야하기 때문에 백트래킹을 활용해 벽 3개를 세울 수 있는 가능한 모든 경우의 수를 생각해 세운 후 바이러스를 퍼트리고 다 퍼진후 안전한 공간의 개수를 세준다.

[문제 링크]

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

[난이도]

- Silver 1

[알고리즘]

- 백트래킹

[코드]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

public class Main {
    static int k;
    static char[] operators;
    static boolean[] visited = new boolean[10];
    static List<String> results = new ArrayList<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        k = Integer.parseInt(br.readLine());

        // 공백을 없애고 각 글자를 char array로 담는다
        operators = br.readLine().replace(" ", "").toCharArray();

        solve("", 0);

        results.sort(String::compareTo); // results 리스트를 사전순으로 정렬

        System.out.println(results.get(results.size() - 1)); // 최댓값
        System.out.println(results.get(0)); // 최솟값
    }

    /**
     *
     * @param num 현재까지 생성된 숫자
     * @param index 현재 처리중인 숫자자리
     */
    static void solve(String num, int index) {
        if (index == k + 1) {
            results.add(num);
            return;
        }

        for (int i = 0; i <= 9; i++) {
            if (visited[i]) continue; // 이미사용한 숫자라면 통과

            // index가 0일경우에는 비교할 숫자가 하나밖에 없기때문에 다음숫자로 넘어감
            // 혹은 비교한 두 숫자가 주어진 부등호의 조건과 맞다면 계속 진행
            if (index == 0 || check(num.charAt(index - 1) - '0', i, operators[index - 1])) {
                visited[i] = true;
                solve(num + i, index + 1);
                visited[i] = false; // 완전탐색을 위해 복구
            }
        }
    }

    static boolean check(int a, int b, char operator) {
        if (operator == '<') return a < b;
        else return a > b;
    }
}

[풀이]

백트래킹 알고리즘을 활용할 때 넘겨주는 매개변수를 num : 현재까지 생성된 숫자, index 현재 처리중인 숫자 를 넘겨준다.

for문을 돌며 숫자 두개를 입력받은 부등호와 비교해 참일경우에만 다음숫자를 진행한다.

[문제 링크]

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

[난이도]

- Gold 5

[알고리즘]

- 백트래킹

[코드]

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        // 초기 신기한 소수 시작 자리 설정
        int[] primeStarts = {2, 3, 5, 7};

        // 결과를 저장할 리스트
        List<Integer> results = new ArrayList<>();

        // 신기한 소수 찾기
        for (int start : primeStarts) { // 일의 자리가 2, 3, 5, 7 이여야함
            findAmazingPrimes(N, start, 1, results);
        }

        // 결과 정렬 및 출력
        Collections.sort(results); // 오름차순으로 정렬 후 출력
        for (int num : results) {
            System.out.println(num);
        }
    }

    // 재귀적으로 신기한 소수를 찾는 함수

    /**
     *
     * @param N N자리
     * @param current 현재 숫자
     * @param length 현재 숫자의 길이
     * @param results 현재 숫자의 길이가 N자리가 되면 results 리스트에 추가함
     */
    private static void findAmazingPrimes(int N, int current, int length, List<Integer> results) {
        if (length == N) { // N자리가 될 때까지 반복
            results.add(current);
            return;
        }

        // 다음 자리수로 확장
        for (int i = 1; i <= 9; i++) {
            int next = current * 10 + i;
            if (isPrime(next)) { // 소수면 true
                findAmazingPrimes(N, next, length + 1, results);
            }
        }
    }

    // 소수 판별 함수
    private static boolean isPrime(int num) {
        if (num < 2) return false; // 2보다 작으면 소수가 아님
        for (int i = 2; i * i <= num; i++) {
            if (num % i == 0) return false; // num이 i로 나눠떨어지면 소수가 아님
        }
        return true;
    }
}

[풀이]

일의 자리가 소수인것은  2, 3, 5, 7 밖에 없으므로 2, 3, 5, 7을 기준으로 신기한 소수를 찾는다. 소수 판별함수는 숫자가 어떤 특정한 수로 나눠떨어지면 소수가 아닌 성질을 활용한다.

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

[난이도]

- Silver 1

[알고리즘]

- DFS

- 완전탐색

- 백트래킹

[코드]

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

public class Main {
    static int N, answer = Integer.MAX_VALUE;
    static int[][] players;
    static boolean[] selected;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());
        players = new int[N][N];
        selected = new boolean[N];

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for (int j = 0; j < N; j++) {
                players[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        solve(0, 0);
        System.out.println(answer);
        br.close();

    }
    static void solve(int depth, int index) {
        if (depth == N/2) {
            int startTeam = 0;
            int linkTeam = 0;

            for (int i = 0; i < N - 1; i++) {
                for (int j = i + 1; j < N; j++) {
                    if (selected[i] && selected[j]) {
                        startTeam += players[i][j];
                        startTeam += players[j][i];
                    } else if (!selected[i] && !selected[j]) {
                        linkTeam += players[i][j];
                        linkTeam += players[j][i];
                    }
                }
            }

            int diff = Math.abs(startTeam - linkTeam);
            answer = Math.min(answer, diff);
            return;
        }
        for (int i = index; i < N; i++) {
            if (!selected[i]) {
                selected[i] = true;
                solve(depth + 1, i + 1);
                selected[i] = false;
            }
        }
    }
}

[풀이]

boolean 배열로 선택한 선수와 선택하지 않은선수를 나눠계산한다.

            for (int i = 0; i < N - 1; i++) {
                for (int j = i + 1; j < N; j++) {
                    if (selected[i] && selected[j]) {
                        startTeam += players[i][j];
                        startTeam += players[j][i];
                    } else if (!selected[i] && !selected[j]) {
                        linkTeam += players[i][j];
                        linkTeam += players[j][i];
                    }
                }
            }

solve의 매개변수로 depth와 index를 주었다.

        for (int i = index; i < N; i++) {
            if (!selected[i]) {
                selected[i] = true;
                solve(depth + 1, i + 1);
                selected[i] = false;
            }
        }

for문을 돌며 선수를 선택할 때 i를 index로주고 선수를 선택했다면 매개변수를 건네줄때 i + 1로 주어 중복탐색을 줄여 시간초과를 방지할 수 있다.

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

[난이도]

- Silver 2

[알고리즘]

- 완전탐색

- DFS

- 백트래킹

[코드]

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

public class Main {
    static int N, answer = Integer.MAX_VALUE;
    static int[][] ingredient;
    static boolean[] selected;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());
        ingredient = new int[N][2];
        selected = new boolean[N];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            ingredient[i][0] = Integer.parseInt(st.nextToken());
            ingredient[i][1] = Integer.parseInt(st.nextToken());
        }
        solve(0, 1, 0, 0);
        System.out.println(answer);
    }

    // 트리의 깊이, 신맛, 쓴맛, 선택한 음식 개수
    static void solve(int depth, int sour, int bitter, int selectedCount) {
        if (depth == N) {
            if (selectedCount != 0) { // 1개 이상의 재료를 선택
                if (Math.abs(sour - bitter) < answer) { // 최솟값으로 갱신
                    answer = Math.abs(sour - bitter);
                }
            }
            return;
        }

        // 완전탐색을 위해 선택한경우와 선택하지 않은 경우를 나누어 진행
        solve(depth + 1, sour * ingredient[depth][0], bitter + ingredient[depth][1], selectedCount + 1); // 선택
        solve(depth + 1, sour, bitter, selectedCount); // 비선택
    }
}

[풀이]

부분집합을 구하는 방식을 활용해 완전탐색을 해야한다.

1. 재료를 선택한 경우와 선택하지 않은 경우 모두를 고려해서 재귀함수를 진행한다.

2. 트리의 깊이가 N이 될때까지 반복한다.

3. 트리의 깊이가 N이면서 1개 이상의 재료를 선택했으며 현재 알고있는 최소값보다 새로구한 값이 더 작을 때 answer를 갱신해준다.

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

[난이도]

- Silver 2

[알고리즘]

- 백트래킹

[코드]

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

public class Main {
    static int N, answer = Integer.MAX_VALUE;
    static int[][] map;
    static boolean[] visited;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());
        map = new int[N][N];
        visited = new boolean[N];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for (int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        for (int i = 0; i < N; i++) {
            visited[i] = true;
            backTracking(i, i, 0, 0);
        }
        System.out.println(answer);
    }

    /**
     * @param start : 메서드 실행 전 위에서 정해줌
     * @param now : 현재 내가 위치한 도시
     * @param sum : 현재위치한 도시까지 사용한 비용
     * @param depth
     */
    static void backTracking(int start, int now, int sum, int depth) {
        if (depth == N - 1) { // 모든 도시를 모두 방문한 경우, N-1인 이유는 백트래킹 메서드를 실행하기 전에 이미 방문함
            if (map[now][start] != 0) { // 마지막 도시에서 처음 도시로 가는 비용 더하기
                sum += map[now][start];
                answer = Math.min(answer, sum); // 최종적으로 나온 비용
            }
            return;
        }
        for (int i = 0; i < N; i++) {
            if (!visited[i]) { // 방문하지 않은 도시일경우
                if (map[now][i] != 0) { // 갈수 있는 도시일경우
                    visited[i] = true; // 방문했다면 true
                    backTracking(start, i, sum + map[now][i], depth + 1);
                    visited[i] = false; // 방문이 끝나면 false
                }
            }
        }
    }
}

[풀이]

시작하는 도시가 1번도시로 고정이 아닌 어느도시에서 시작하든 최소비용을 찾는것이기 때문에 N번 반복한다.

        for (int i = 0; i < N; i++) {
            visited[i] = true;
            backTracking(i, i, 0, 0);
        }

백트래킹 메서드의 매개변수 start 는 순회를 시작한 도시의 위치로 메서드를 실행할 때 정해진다.

매개변수 now는 현재 내가 위치한 도시의 위치를 뜻한다. 

매개변수 sum은 현재 내가 now에 올때까지 사용한 비용을 뜻한다.

매개변수 depth는 모든도시를 순회했는지 체크한다.

for문을 돌며 방문하지 않은 도시이며 map[i][j]가 0이 아닌도시(방문할 수 있는 도시) 라면 백트래킹을 재귀적으로 수행한다.

이때 넣어주어야 하는 매개변수들은 순회를 시작한 도시 start, 다음 방문할 도시 i, 현재까지 사용한 비용(sum) + 현재 위치에서 i까지 가는 비용(map[now][i]), depth + 1이다.

        for (int i = 0; i < N; i++) {
            if (!visited[i]) { // 방문하지 않은 도시일경우
                if (map[now][i] != 0) { // 갈수 있는 도시일경우
                    visited[i] = true; // 방문했다면 true
                    backTracking(start, i, sum + map[now][i], depth + 1);
                    visited[i] = false; // 방문이 끝나면 false
                }
            }
        }

depth 가 N-1이 되면 모든도시를 방문한 것이다. depth가 N이아닌 N-1인 이유는 순회를 시작한 도시는 메서드 실행전 체크하기 때문이다.

depth가 N-1이 되었다면 마지막 도착한 도시에서 순회를 시작한 도시로 돌아와야하기 때문에 map[now][start] != 0 이라면

sum += map[now][start]를 해주어 마지막 비용을 추가해준다.

        if (depth == N - 1) { // 모든 도시를 모두 방문한 경우, N-1인 이유는 백트래킹 메서드를 실행하기 전에 이미 방문함
            if (map[now][start] != 0) { // 마지막 도시에서 처음 도시로 가는 비용 더하기
                sum += map[now][start];
                answer = Math.min(answer, sum); // 최종적으로 나온 비용
            }
            return;
        }

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

[난이도]

- Silver 2

[알고리즘]

- 백트래킹

[코드]

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

public class Main {
    static int k;
    static int[] arr, list;
    static boolean[] checked;
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        while (true) {
            st = new StringTokenizer(br.readLine(), " ");
            k = Integer.parseInt(st.nextToken());
            if (k == 0) { // 0일경우 종료
                break;
            }
            arr = new int[k];
            list = new int[6];
            checked = new boolean[k];
            for (int i = 0; i < k; i++) {
                arr[i] = Integer.parseInt(st.nextToken());
            }
            backTracking(0, 0);
            bw.write("\n");
        }
        bw.flush();
        bw.close();
        br.close();
    }

    static void backTracking(int depth, int start) throws Exception{
        if (depth == 6) {
            for (int i : list) {
                bw.write(i + " ");
            }
            bw.write("\n");
            return;
        }
        for (int i = start; i < k; i++) { // i 는 start부터 시작
            if (!checked[i]) { // 사용하지 않은 숫자만 허용
                checked[i] = true;
                list[depth] = arr[i];
                backTracking(depth + 1, i + 1); // i+1을 해주어 중복을 막음
                checked[i] = false;
            }
        }
    }
}

[풀이]

1. 입력을 받는다. k가 0일경우 종료한다. 입력받은숫자는 arr 배열에 저장한다.

2. 백트래킹 알고리즘을 수행한다. 매개변수로 depth, start를 받는다. 0, 0부터 시작.

3. for문을 돌며 arr에 담긴 숫자를 list에 담아준다. for문은 i = start부터 시작.

4. 숫자를 list배열에 담아준 후 depth+1, i+1로 재귀적으로 호출해준다.

5. depth가 6일경우 list배열에 담겨있는 숫자를 출력해준다.

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

[난이도]

- Silver 3

[알고리즘]

- 백트래킹

[코드]

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

public class Main {
    static int N, M;
    static boolean[] checked;
    static int[] arr, tmp;
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        checked = new boolean[N];
        arr = new int[N];
        tmp = new int[N];

        st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(arr); // 오름차순 정렬
        backTracking(0, 0);
        bw.flush();
    }

    static void backTracking(int depth, int start) throws Exception {
        if (depth == M) { // depth 가 M이 될때까지 실행
            for (int i = 0; i < M; i++) {
                bw.write(tmp[i] + " ");
            }
            bw.write("\n");
            return;
        }

        for (int i = start; i < N; i++) {
            tmp[depth] = arr[i];
            backTracking(depth + 1, i);
        }
    }
}

[풀이]

사용한 숫자를 중복해서 사용하기 위해 boolean 배열을 사용하지 않는다.

비내림차순을 만족하기위해 매개변수를 depth 이외에 하나를 추가해준다. 매개변수는 i로 준다.