[알고리즘] 가르침 (백준 1062번)

1062번: 가르침

 백트랙킹을 통한 완전탐색을 하는 문제다. 비트마스크와 배열 둘 중 하나를 이용해서 풀 수 있다. 2개의 메모리, 시간 효율 차이는 거의 없다. 그냥 똑같은 수준이다.

 

Solution

 공통적으로 행해야 할 것은 우선 가르칠 수 있는 단어가 5개 미만이면 어떤 글자도 읽을 수 없다.

만약 5개 이상이라면 남극언어의 기본 시작단어, 끝단어를 이루고 있는 알파벳들 'a c t n i' 5가지부터 추가시키고 시작한다.

1. boolean 배열로 가르침 여부 체크

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;


public class Main {

	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

	static int N, K;
	static String[] words;
	static boolean[] visited = new boolean[26];
	static int max = 0;

	public static void solution() throws Exception
	{
		StringTokenizer strtok = new StringTokenizer(br.readLine());
		N = Integer.parseInt(strtok.nextToken());
		K = Integer.parseInt(strtok.nextToken());

		words = new String[N];

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

		//5글자보다 작으면 a c t n i도 못읽음
		if(K < 5)
		{
			bw.write("0");
			return;
		}

		//5글자 이상 가르칠 수 있다면 무조건 a c t n i부터 가르침
		visited['a'-'a'] = true;
		visited['c'-'a'] = true;
		visited['t'-'a'] = true;
		visited['n'-'a'] = true;
		visited['i'-'a'] = true;
		backTracking(0, 5);
		bw.write(max+"");

	}

	static void backTracking(int index, int depth)
	{
		if(depth == K)
		{
			//읽을 수 없는 단어가 나올 때마다 1개씩 깎음
			int count = N;
			
			for(int i = 0;i < N;i++)
			{
				String word = words[i];

				for(int j = 0;j < word.length();j++)
				{
					//가르친 단어 x
					if(!visited[word.charAt(j) - 'a'])
					{
						count--;
						break;
					}
				}
			}

			max = Math.max(count, max);
		}
		else
		{
			for(int i = index;i < 26;i++)
			{
				if(!visited[i])
				{
					visited[i] = true;
					backTracking(i + 1, depth + 1);
					visited[i] = false;
				}
			}
		}
	}


	public static void main(String[] args) {
		try
		{
			solution();
			bw.close();
			br.close();
		}
		catch (Exception e)
		{
			e.printStackTrace();
		}
	}

}

 

2. 비트마스크로 가르침 여부 체크

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;


public class Main {

	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

	static int N, K;
	static String[] words;
	static int max = 0;

	public static void solution() throws Exception
	{
		StringTokenizer strtok = new StringTokenizer(br.readLine());
		N = Integer.parseInt(strtok.nextToken());
		K = Integer.parseInt(strtok.nextToken());

		words = new String[N];

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

		//5글자보다 작으면 a c t n i도 못읽음
		if(K < 5)
		{
			bw.write("0");
			return;
		}

		//5글자 이상 가르칠 수 있다면 무조건 a c t n i부터 가르침
		int result = 0;
		result |= (1 << ('a'- 'a'));
		result |= (1 << ('c'- 'a'));
		result |= (1 << ('t'- 'a'));
		result |= (1 << ('n'- 'a'));
		result |= (1 << ('i'- 'a'));

		backTracking(0, 5, result);
		bw.write(max+"");
	}

	static void backTracking(int index, int depth, int result)
	{
		if(depth == K)
		{
			//읽을 수 없는 단어가 나올 때마다 1개씩 깎음
			int count = N;

			for(int i = 0;i < N;i++)
			{
				String word = words[i];

				for(int j = 0;j < word.length();j++)
				{
					//가르친 단어 x
					if(!isCharacterIn(word.charAt(j), result))
					{
						count--;
						break;
					}
				}
			}

			max = Math.max(count, max);
		}
		else
		{
			for(int i = index;i < 26;i++)
			{
				if(!isCharacterIn((char)(i+'a'),result))
				{
					result |= (1 << i);
					backTracking(i + 1, depth + 1, result);
					result &= ~(1 << i);
				}
			}
		}
	}

	//해당 글자를 가르쳤는지 확인
	static boolean isCharacterIn(char c, int result)
	{
		if((result & (1 << (c-'a'))) > 0)
			return true;
		return false;
	}

	public static void main(String[] args) {
		try
		{
			solution();
			bw.close();
			br.close();
		}
		catch (Exception e)
		{
			e.printStackTrace();
		}
	}

}