<stdio.han>

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를 갱신해준다.

백준 2468번: 안전 영역[JAVA]

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

[정답 코드]

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

public class Main {
    static int N,result, count, nx, ny;
    static int[][] graph;
    static boolean[][] visited;
    static int[] dx = {0, 0, 1, -1}; // 상하좌우 4방탐색
    static int[] dy = {1, -1, 0, 0};
    static ArrayList<Integer> list = new ArrayList<>();
    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 = new StringTokenizer(br.readLine(), " ");


        // graph 초기화
        N = Integer.parseInt(st.nextToken());
        graph = new int[N][N];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for (int j = 0; j < N; j++) {
                graph[i][j] = Integer.parseInt(st.nextToken());

                // 건물의 높이들이 담긴 리스트
                if (!list.contains(graph[i][j])) { // 중복체크
                    list.add(graph[i][j]);
                }
            }
        }

        result = 1;
        for (Integer height : list) { // 0부터 끝까지 탐색하는것은 비효율적이기 때문에 리스트 활용
            count = 0;
            visited = new boolean[N][N];
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (!visited[i][j] && graph[i][j] >= height) {
                        count++;
                        dfs(height, i, j);
                    }
                }
            }
            result = Math.max(result, count); // 새로탐색한결과 중에 더 큰값 저장
        }
        System.out.println(result);
    }

    static void dfs(int height, int x, int y) {
        visited[x][y] = true;
        // 4방탐색
        for (int i = 0; i < 4; i++) {
            nx = x + dx[i];
            ny = y + dy[i];
            if (nx >= 0 && ny >= 0 && nx < N && ny < N) { // 그래프 범위 안에 있을 경우
                if (!visited[nx][ny]) { // 방문하지 않은 건물인 경우
                    if (graph[nx][ny] >= height) { // 그 건물이 물의 높이보다 높을 경우
                        dfs(height, nx, ny);  // 상하좌우 인접한 건물을 찾는다
                    }
                }
            }
        }
    }

}

[설명]

이 문제는 완전탐색 알고리즘이다. 그중 dfs 알고리즘을 활용해 문제를 해결했다. dx/dy 기법을 활용한 4방 탐색도 활용했다. 먼저 2차원 배열을 선언해준다. 이 때 중요한점이 입력값들을 중복값을 체크하며 리스트에 담아놔야한다. 그렇지 않을 경우는 비의 양을 0부터 끝까지 중복탐색해야해서 메모리 초과가 나거나 비효율적이다. 

dfs 로직은 4방탐색을 하며 그 범위가 방문하지않은 건물이며 그 건물이 물의 높이 보다 높을경우 dfs를 다시 실행한다. 

그 후 결과값을 비교해 최대값을 출력한다.

백준 1182번: 부분수열의 합[JAVA]

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

[정답 코드]

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

public class Main {
    static int N, S, result = 0;
    static int[] subsequence;

    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 = new StringTokenizer(br.readLine(), " ");

        N = Integer.parseInt(st.nextToken()); // 정수의 개수
        S = Integer.parseInt(st.nextToken()); // 타깃 넘버
        subsequence = new int[N];

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

        dfs(0, 0);


        if (S == 0) { // S가 0일 때 result--
            result--;
        }
        System.out.println(result);


        bw.flush();
        bw.close();
        br.close();
    }

    public static void dfs(int depth, int sum) {
        if (depth == N) { // depth 가 마지막까지 갔을 경우
            if (sum == S) { // 그 중에 sum 이 타깃 넘버일 경우
                result++;
            }
            return;
        }
        dfs(depth + 1, sum + subsequence[depth]); // 원소를 선택했을 경우의 수열의 합
        dfs(depth + 1, sum); // 원소를 선택하지 않았을 경우의 수열의 합
    }
}

[설명]

이 문제는 브루트 포스 알고리즘 그중에 dfs알고리즘을 이용해 풀수있는 문제이다. 문제 설명을 하자면 숫자가 주어지면 그 수를가지고 만들 수 있는 모든 부분수열을들중 부분수열들의 합이 S 인 경우의 수를 출력하는 문제이다.

예를 들면 숫자가 1, 2, 3 이 주어졌다면 가능한 부분수열은 {1}, {1, 2}, {1, 2, 3}, {2}, {2, 3}, {3} 이다. 수열들의 모습을 보면 브루트포스 알고리즘을 활용했을때의 결과 같이 생겼다.

코드로 구현했을 경우 한 가지 문제가 있다. S가 0일경우이다.  dfs 로직을 실행할 때 부분수열들의 합이 담기는 변수 sum 이 처음에 0을 초기화가 되어있기 때문에 원소를 아무것도 선택하지 않는다면 부분수열의 합이 0이라고 계산되기 때문이다. 그렇기 때문에 S가 0일경우 마지막에 결과값에 1을 빼주어야한다.

백준 1759번: 암호 만들기[JAVA]

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

[정답 코드]

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

public class Main {
    static int L, C;
    static char[] code;
    static char[] arr;
    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(), " ");

        L = Integer.parseInt(st.nextToken()); // 암호의 길이
        C = Integer.parseInt(st.nextToken()); // C개의 소문자

        code = new char[L]; // 암호를 저장할 배열
        arr = new char[C]; // 알파벳 입력받을 배열

        st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < C; i++) {
            arr[i] = st.nextToken().charAt(0); // 초기화
        }
        Arrays.sort(arr); // 사전순으로 정렬

        dfs(0, 0); //로직 실행
    }

    public static void dfs(int depth, int start) {
        // depth 가 L일 경우 종료
        if (depth == L) {
            if (isValid(code)) { // 자음,모음 체크하는 로직 실행 후 true 일 경우에만 출력
                for (char c : code) {
                    System.out.print(c);
                }
                System.out.println();
            }
            return;
        }
        for (int i = start; i < C; i++) {
            code[depth] = arr[i]; // 코드배열 입력
            dfs(depth+1, i+1); // depth 한칸 깊이, start 위치 한칸 이동
        }
    }

    // 자음이 2개이상 모음이 1개 이상인지 판별하는 로직
    public static boolean isValid(char[] code) {
        int c = 0; // 자음의 수
        int v = 0; // 모음의 수
        for (int i = 0; i < code.length; i++) {
            if (code[i] == 'a' || code[i] == 'e' || code[i] == 'i' || code[i] == 'o' || code[i] == 'u') {
                v++; // 모음일 경우 v++
            } else {
                c++; // 자음일 경우 c++
            }
        }
        if (c >= 2 && v >= 1) {
            return true; // 자음 2개 이상, 모음 1개이상 일 경우 true 반환
        } else {
            return  false; // 아닐경우 false 반환
        }
    }
}

[설명]

완전탐색(브루트 포스) 알고리즘을 이용해 문제를 풀었다. 그 이유는 '해' 가 가능한 모든 경우의 수를 탐색한 후, 조건에 해당하는 해를 '모두' 출력해야하는 문제이기 때문이다. 완전탐색 알고리즘 중의 하나인 DFS 알고리즘을 이용해 문제를 풀었다.

문제의 해결방법의 순서를 대략적으로 설명하자면

1. 문자열을 입력받는다.

2. 입력받은 문자열을 이용해 depth 가 L이 될때 까지 dfs 를 한다.

3. 결과값이 조건을 통과할 경우 출력한다.