목록백트래킹 (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()..
[백준 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
[백준 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..
[백준 17142] 연구소 3
백트래킹으로 바이러스를 모두 활성화 해보면서 모든 경우의 수를 체크한다. 시간제한이 굉장히 짧으므로 중복되는 백트래킹이 없어야한다. 예를들어, 바이러스 1번, 2,번 3번 을 활성화 한 후 BFS를 마쳤으면 1번, 3번, 2번 과 같은 경우는 없어야한다. 이는 백트래킹할때 변수를 넘겨주며 현재 활성화 한 바이러스번호 보다 높은 바이러스만을 활성화하게 하면 된다. public class Main { static int n; static int m; static int a[][]; static ArrayList virus = new ArrayList(); static int dx[] = {-1, 1, 0, 0}; static int dy[] = {0, 0, -1, 1}; static int min = Int..
[백준 14889] 스타트와 링크
백트래킹으로 가능한 모든 팀을 구성한 뒤 최솟값을 구했다. 위의 예제로 설명하겠다. 1. 인덱스별로 DFS를 한다. 2. n/2 일때 방문한 노드2개 방문안한 노드2개 이므로 방문한 쪽/ 안한 쪽으로 팀을 나눈다. 3. 배열이나 리스트에 각 노드를 담아서 능력치 차이를 계산한다. 백트래킹을 제외하면 자기 스타일대로 구현을 하면 된다. public class Main { static int n; static int a[][]; static boolean visited[]; static int min = Integer.MAX_VALUE; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader..
[백준 문제집] N과 M 시리즈
문제 전문 이미지는 생략하도록 하겠다. N과 M 시리즈는 모~~두 백트래킹 문제로 시리즈별로 난이도 차이는 거의 없다. 백트래킹을 모른다면 간단히 공부하고 오거나 천재라면 필자의 빈약한... 소스를 보고 이해하면 되겠다. 15649번 : N과 M(1) ...더보기 중복없는 수열을 뽑아야 하므로 방문배열을 만들어 주어야 한다. 낮은 번호부터 순서대로 진행하며 배열체크만 해주면 된다. public class Main { static int n; static int m; static boolean visited[]; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStr..
[백준 1405] 미친 로봇
완전탐색으로 로봇이 이동할 경로를 모두 체크해야 한다. 구현은 쉽지만 문제 해석이 잘 안되어서 참조하여 풀었다. 로직을 직접 해석하는 편이 좋을 것 같다. public class Main { static boolean visited[][] = new boolean[29][29]; static double a[] = new double[4]; static int dr[] = {-1, 1, 0, 0}; static int dc[] = {0, 0, -1, 1}; static double result = 0; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamRe..
[백준 17136] 색종이 붙이기
DFS + 백트래킹 활용 문제이며, 색종이를 최소한으로 사용하려면 큰 종이부터 사용해야 한다는 점에서 그리디한 방식도 섞여있다. 1. 색종이 개수 정보를 담은 배열을 만든다. 2. 10x10 배열을 탐색하며 값이 1일 경우 5x5, 4x4, ..., 1x1 순으로 검사하며 붙일 수 있다면 붙인다. 3. 1을 모두 메꿀 수 없다면 최소값 갱신이 안되므로 -1을 출력한다. 4. DFS 도중 이미 최소값보다 색종이 사용 수가 크다면 함수를 종료해준다. 제한시간이 1초라서 가지치기를 해주었다. public class Main { static int paper[] = {0, 5, 5, 5, 5, 5}; static int a[][] = new int[10][10]; static int min = 100; publ..