목록DFS (26)
Dev.baelanche
[백준 11580] Footprint
명령어의 수가 최대 1000이므로 2000*2000의 배열공간만 있으면 모든 경우를 저장할 수 있다. 한번이라도 가본 좌표를 체크해주기만 하면 된다. public class Main { static int l; static char c[]; static boolean visited[][] = new boolean[2001][2001]; public static void main(String[] args) { Scanner sc = new Scanner(System.in); l = sc.nextInt(); c = sc.next().toCharArray(); dfs(1000, 1000, 0); int cnt = 0; for(int i=0; i
[백준 1389] 케빈 베이컨의 6단계 법칙
문제가 엄청긴데 요약하자면 그래프에서 A에서 B로 가는데 몇단계를 거치는지 구하라는 얘기이다. 유저가 3명일때 1 : 1->2 , 1->3 2 : 2->1 , 2->3 3 : 3->1 , 3->2 노드 별로 n-1만큼의 경우가 있고 이 경우의 합이 가장 작은 노드의 번호를 구하면 된다. 양방향 그래프를 구현한 후 DFS나 BFS로 간선을 몇번 탔는지 구한다. public class Main { static int n; static int a[][]; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokeni..
[백준 13901] 로봇
문제에서 요구하는대로 로봇을 움직여주면 된다. 필자는 DFS로 풀었다. 흠.. 그냥 DFS문제라서 추가적으로 언급할 얘기는 없다;; public class Main { static int r; static int c; static int a[][]; static int d[] = new int[4]; static int lx; static int ly; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st; st = new StringTokenizer(br.readLine()); r = In..
[백준 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..
[백준 2661] 좋은수열
최소값을 구해야 하므로 조건을 만족하는 수 중 가장 작은것을 우선 출력하게 해야한다. 그리디하게 생각해보면 첫번째 수는 무조건 1이 된다. 수를 이어붙일 때마다 좋은 수열인지 여부를 체크해준다. 11 : 수의 길이가 2이면 1번만 검사하면 된다. 1212 : 수의 길이가 4이면 밑줄친 1과 2 검사 1번 + 12, 12 검사 1번, 총 2번해야 한다. 123123 : 수의 길이가 6이면 2,3 / 31, 23 / 123, 123 총 3번해야 한다. 따라서 검사 횟수는 수의 길이/2이다. 검사할 인덱스 지정은 의식의 흐름대로 하여서 로직을 보는 편이 좋을 듯 하다. public class Main { static int n; public static void main(String[] args) throws..