목록완전탐색 (16)
Dev.baelanche
[백준 11578] 팀원 모집
N, M 이 최대 10으로 충분히 작기 때문에 완전탐색으로 문제를 풀 수 있다. 백트래킹으로 모든 경우를 되집어보며 구해주었다. public class Main { static int n; static int m; static int a[][]; static boolean visited[]; static int min = Integer.MAX_VALUE; public static void main(String[] args) { Scanner sc = new Scanner(System.in); n = sc.nextInt(); m = sc.nextInt(); a = new int[11][11]; visited = new boolean[11]; for(int i=1; i0) { a[i][sc.nextInt()..
[백준 7453] 합이 0인 네 정수
A, B, C, D 배열의 각각을 더해서 0과 비교하기에는 시간이 너무 오래걸린다. 1. A, B의 모든 부분합을 저장한 배열을 만든다. (C, D의 부분합 배열이어도 상관없다.) 2. C, D의 모든 부분합을 저장한 Map을 만든다. 부분합 중 중복된 수가 있다면 카운트를 올린다. Map의 Key를 sum, Value를 카운트로 사용했다. 3. A, B의 부분합 배열과 Map의 원소들을 비교하며 두 원소의 합이 0일 경우 카운트만큼 개수를 올린다. 코드는 알아보기 꽤나 쉽다. public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int temp..
[백준 10974] 모든 순열
신나는 완전탐색 문제다. 방문배열을 백트래킹 하며 진행했다. public class Main { static int n; static boolean visited[]; public static void main(String[] args) { Scanner sc = new Scanner(System.in); n = sc.nextInt(); visited = new boolean[n+1]; dfs(0, ""); } public static void dfs(int cnt, String s) { if(cnt == n) { System.out.println(s); return; } for(int i=1; i
[백준 2589] 보물섬
육지중에 가장 멀면서 빠른 길을 찾으라는 문제이다. 문맥이 참;; 배열 크기가 50*50이니 육지인 인덱스마다 BFS를 해주며 완전탐색하면 된다. public class Main { static int n; static int m; static int a[][]; static boolean visited[][]; static int dx[] = {-1, 0, 0, 1}; static int dy[] = {0, -1, 1, 0}; static int max = 0; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); Stri..
[백준 14500] 테트로미노
N*M 배열에서 테트로미노를 놓을 수 있는 경우를 모두 체크한다. 코드를 보면 구현방식을 아주 쉽게 알 수 있다. public class Main { static int a[][]; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st; st = new StringTokenizer(br.readLine()); int n = Integer.parseInt(st.nextToken()); int m = Integer.parseInt(st.nextToken()); a = new int[n][m]; ..
[백준 6603] 로또
중복되지 않으면서 오름차순인 수열을 완전탐색한다. 빈 줄을 끼워넣는 것을 유의한다. public class Main { static int a[]; static int k; static boolean f = true; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st; while(true) { st = new StringTokenizer(br.readLine()); k = Integer.parseInt(st.nextToken()); if(k == 0) break; a = new int[k..
[백준 15683] 감시
감시카메라가 감시 가능한 모든 지역을 탐색하게 한다. 1번은 4가지 경우, 2번은 2가지, 3번은 4가지, 4번도 4가지, 5번은 1가지 경우가 있다. 모든 경우를 완전탐색하기만 하면 되는 문제인데 구현이 좀 까다롭다. public class Main { static int n; static int m; static ArrayList cctv = new ArrayList(); static int ans = Integer.MAX_VALUE; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st..
[백준 15686] 치킨 배달
백트래킹으로 모든 집에 대해 치킨거리를 구해야 한다. 배열을 쓰는 것보다는 집, 치킨집을 리스트에 담아서 구현하는게 빨라서 이중루프로 치킨거리를 구하게 했다. 치킨집 중에 M개 만큼의 치킨집을 골라 스택에 담아 백트래킹으로 탐색했고, 리스트를 쓰든 벡터를 쓰던 상관은 없다. 이 문제 역시 중복없는 완전탐색이 핵심이다. public class Main { static int n; static int m; static ArrayList h = new ArrayList(); static ArrayList ch = new ArrayList(); static Stack choice = new Stack(); static int ans = Integer.MAX_VALUE; public static void main..