[SDS 알고리즘 특강 복습] 1062 가르침 (DFS / 백트래킹)

아이디어를 못떠올려서 정답 코드 참고하면서 풀었음.

 

문제의 핵심 아이디어는 다음과 같음

 

1. a~z의 문자에 대해 dfs를 돌려 모든 문자의 조합을 탐색한다.

2. 이때 문자갯수가 K와 같아지면 몇단어셀 수 있는지 체크하고 max값 업데이트한 뒤 return한다.

 

지금까지 그래프의 좌표에 대해서만 dfs를 돌려야한다는 고정관념이 있어 문자에 대해 dfs를 돌리는 것을 상상을 못했다. 좌표뿐만 아니라 문제에서 설정된 무언가에 대해 돌릴 수 있다는 걸 간과하지말자.

 

맞았습니다를 받아냈지만, 컨디션이 안좋아서 강사님 코드 3번정도 참고했다..!

반드시 다시 복습해내자.

 

<내 정답 코드>

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

    static int N, K;
    static int visited[];
    static String word[];
    static int max = 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());

        word = new String[N];

        for(int i=0; i<N; i++) {
            word[i] = br.readLine();
        }

        visited = new int[26];
        visited['a' - 'a'] = 1;
        visited['n' - 'a'] = 1;
        visited['t' - 'a'] = 1;
        visited['i' - 'a'] = 1;
        visited['c' - 'a'] = 1;

        if (K < 5) {
            System.out.println(0);
            return;
        }

        dfs(0, 5);
        System.out.println(max);

    }

    static void dfs(int cur, int count) {
        if(count == K) {
            int num = 0;
            for(int i=0; i<N; i++) { // N개의 단어 체크
                int flag = 0;
                for(int j=4; j<word[i].length()-4; j++) { // 한 단어의 중간부분 체크
                    if(visited[word[i].charAt(j) - 'a'] == 0) {
                        flag = 1;
                        break;
                    }
                }
                if(flag == 0) {
                    num++;
                }
            }
            max = Math.max(max, num);
            return;
        }

        for(int i=cur; i<26; i++) {
            if(visited[i] == 0) {
                visited[i] = 1;
                dfs(i+1, count+1);
                visited[i] = 0;
            }
        }

    }

}