https://www.acmicpc.net/problem/4991 4991번: 로봇 청소기 각각의 테스트 케이스마다 더러운 칸을 모두 깨끗한 칸으로 바꾸는 이동 횟수의 최솟값을 한 줄에 하나씩 출력한다. 만약, 방문할 수 없는 더러운 칸이 존재하는 경우에는 -1을 출력한다. www.acmicpc.net 필요한 배경지식 1번 풀이 : DFS, BFS 2번 풀이 : BFS, 외판원 문제(TSP) 3번 풀이 : BFS, DP, 비트마스킹 문제 해결 방법 방의 크기가 최대 20*20이므로 최단경로를 구하기 위해 BFS를 한번 수행하는 시간은 크게 문제가 되지 않습니다. 더러운 칸의 개수가 10개이므로 BFS를 최대 11번 수행하여 모든 더러운 칸과 로봇청소기 사이의 거리를 어렵지 않게 구할 수 있습니다. (di..
www.acmicpc.net/problem/9997 9997번: 폰트 첫째 줄에 단어의 개수 N (1 ≤ N ≤ 25)가 주어진다. 다음 N개 줄에는 사전에 포함되어있는 단어가 주어진다. 단어의 길이는 100을 넘지 않으며, 중복되는 단어는 주어지지 않는다. www.acmicpc.net 필요한 배경지식 비트마스킹, 조합론에 대한 지식이 필요합니다. 문제 해결 방법 문제에서 구해야 할 테스트문장은 N개의 단어를 조합하여 만들 수 있으며 소문자'a'부터 'z'까지 26개가 문장에 모두 포함되어 있어야 합니다. 어떻게 N개의 단어를 조합하여 테스트 문장을 만들 수 있을지 생각해 보기전에, 문장안에 a~z까지의 문자가 존재하는지 확인할 방법을 먼저 생각해 봅시다. 확인할 개수가 26개밖에 되지 않기 때문에 가장..