[백준][boj]가르침 (JAVA) - 완전탐색의 유연한 생각

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

 

 

 

 

✔ 문제파악

• 첫번 째 줄에 단어의 개수 N과 배울 수 있는 글자 수 K가 주어진다. 그리고 단어 배열이 주어진다.
• 선생님은 학생들에게 K개의 글자를 가르칠 수 있는데, K개의 글자를 가르친 후 학생들이 읽을 수 있는 단어의 개수가 최대인 값이 무엇인지 구하여라.
  • 접두사는 "anta", 접미사는 "tica"로 끝난다.

 

 

 

 

✔ 접근방법

백트래킹(DP 문제), 브루트포스 알고리즘

 

1) 단어 배열을 예쁘게 만들어 준 후, 공통된 접두사와 접미사에 포함된 글자를 방문 처리해준다.

=> 우리는 배운 글자를 boolean 방문 배열을 통해 해결해줄 것이다 ! 

•  visited['a' - 97]을 빼주는 이유는 소문자 a의 아스키코드가 97이기 때문. 
  🎐 아스키코드를 잘 모르겠으면 https://namu.wiki/w/%EC%95%84%EC%8A%A4%ED%82%A4%20%EC%BD%94%EB%93%9C

=> 공통적으로 포함된 "anta"와 "tica"는 시간을 줄이기 위해 정제한 후, 단어 배열에 추가해준다.

=> antic는 무조건 배워야하는 단어이므로 방문처리 해준다.

// 1) 단어 정제
for (int i = 0; i < n; i++) {
    String word = br.readLine();
    arr[i] = word.replaceAll("[a|n|t|i|c]", "");
}

// a,n,t,i,c 방문처리
static boolean[] visited = new boolean[27];
visited['a' - 97] = visited['n' - 97] = visited['t' - 97] = visited['i' - 97] = visited['c' - 97] = true;

 

 

 

2) 백트래킹 시작

static void dp(int depth, int start) {
        // 정해진 수 만큼의 단어를 외우면 종료(종료조건)
        if (depth == k - 5) {
            result = 0;

            for (int i = 0; i < n; i++) {
                if (check(arr[i])) {
                    result++;
                }
            }
            MAX_VALUE = Math.max(result, MAX_VALUE);

            return;
        }

        for (int i = start; i < 27; i++) {
            if (!visited[i]) {
                visited[i] = true;
                dp(depth + 1,i);
                visited[i] = false;
            }
        }
    }

	// 단어에 있는 모든 글자를 배웠는지 확인
    static boolean check(String word) {
        for (int i = 0; i < word.length(); i++) {
            if (!visited[word.charAt(i) - 97]) {
                return false;
            }
        }
        return true;
    }

 

💭 브루트포스, 백트래킹, DFS 차이
브루트 포스 알고리즘 = 모든 가능한 경우를 전부 해보는 방식의 알고리즘
백트래킹 = 탐색을 진행하고 조건에 맞지 않는 부분을 제외하면서 진행하는 방식의 알고리즘
DFS = 트리를 완전 탐색하는 한가지 방법

 

 

 

 

 

 

✔ 전체코드

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

public class Main {
    static int n;
    static int k;
    static String[] arr;
    static int MAX_VALUE = 0;
    // 배운 글자를 표시할 방문 배열 생성
    static boolean[] visited = new boolean[27];

    static int result = 0;

    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());
        k = Integer.parseInt(st.nextToken());

        arr = new String[n];

        // 1) 단어 정제 및 방문처리
        for (int i = 0; i < n; i++) {
            String word = br.readLine();
            arr[i] = word.replaceAll("[a|n|t|i|c]", "");
        }
        visited['a' - 97] = visited['n' - 97] = visited['t' - 97] = visited['i' - 97] = visited['c' - 97] = true;

        if (k < 5) {
            System.out.println(0);
        } else {

            dp(0,0);

            System.out.println(MAX_VALUE);
        }

    }

    static void dp(int depth, int start) {
        // 정해진 수 만큼의 단어를 외우면 종료(종료조건)
        if (depth == k - 5) {
            result = 0;

            for (int i = 0; i < n; i++) {
                if (check(arr[i])) {
                    result++;
                }
            }
            MAX_VALUE = Math.max(result, MAX_VALUE);

            return;
        }

		// start 인덱스를 통해 중복을 방지해준다.
        for (int i = start; i < 27; i++) {
            if (!visited[i]) {
                visited[i] = true;
                dp(depth + 1,i);
                visited[i] = false;
            }
        }
    }

    static boolean check(String word) {
        for (int i = 0; i < word.length(); i++) {
            if (!visited[word.charAt(i) - 97]) {
                return false;
            }
        }
        return true;
    }
}

 

 

 

 

 

 

🐥 회고

3번째 풀고 있는 코드이다. (재귀는 어려워)

시간 초과가 나와서 애를 먹었다. 예외처리를 연습하는 방법이 조금 더 필요할 것 같다 
I can do it !!!!!!