Dev.baelanche

문제의 해석이 좀 난해했다. 지문에서 알 수 있는 것은 1. 수는 1부터 N까지로 구성되어 있으며 연속된 수열이 아니면 제대로 복구된 수열이 아니다. 2. 수는 50을 넘지 않는다. 위 힌트를 바탕으로 풀이해보자. 1. DFS + 백트래킹으로 접근한다. 2. 수의 사용여부를 기록하는 배열을 만들어서 한번만 사용할 수 있게 한다. 3. 2의 조건을 만족할때 한글자씩 탐색한다. 4. 2의 조건을 만족하고 두글자가 50이하일 경우 탐색한다. 5. 입력받은 수열의 끝까지 탐색을 마칠 경우 수열을 검사하고 만족시 종료한다. public class Main { static String s; static boolean used[] = new boolean[51]; static int a[] = new int[50];..

81칸 중에 비어있는 칸이 있다면 백트래킹으로 하나하나 채워간다. 수를 채울 때 가로줄, 세로줄, 3x3칸에 중복되는 수가 없게한다. public static boolean inputNumber(int r, int c, int num) { for(int i=0; i

N*N의 체스판에 N개의 퀸을 놓는 경우를 모두 체크해야 한다. N개의 퀸을 모두 움직여봐야 하므로 백트래킹을 사용한다. 백트래킹은 설명이 좀 난해하여 로직을 서술하겠다. 퀸은 가로, 세로, 대각선으로 움직이는 말이라는 것을 사전에 알아야 한다. 코드 1 public class Main { static int n; static int a[][]; static int cnt = 0; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); n = Integer.parseInt(br.readLine()); a = new int[n+..

보드에서 모든 경우를 탐색해야 하기 때문에 백트래킹을 활용한다. static boolean alpha[] = new boolean[26]; static boolean visited[][]; static int dr[] = {-1, 1, 0, 0}; static int dc[] = {0, 0, -1, 1}; 1. 알파벳은 최대 1번만 사용 가능하기 때문에 배열을 만들어 각 알파벳 별로 사용했는지 여부를 체크한다. 2. DFS 도중 같은 지점은 방문할 수 없으므로 방문기록 배열을 만든다. 3. 상하좌우로 이동하기 때문에 방향배열을 만든다. if(!visited[nr][nc] && !alpha[a[nr][nc] - 'A']) { visited[nr][nc] = true; alpha[a[nr][nc] - 'A'..

DFS로 완전탐색하여 조건에 맞는 암호를 모두 찾아내면 된다. 1. 사전식으로 출력해야 하므로 입력받은 배열은 오름차순으로 정렬한다. 2. 재귀 + 반복문으로 진행하며 현재의 문자보다 큰 문자가 나오면 문자를 카운트했을때와 안했을때로 분기한다. 3. 문자를 카운트 할때마다 자음인지 모음인지 체크한다. 4. l 과 문자의 길이가 같고 자음, 모음의 조건을 만족하면 출력한다. public class Main { static int l; static int c; static char a[]; public static void main(String[] args) { Scanner sc = new Scanner(System.in); l = sc.nextInt(); c = sc.nextInt(); a = new c..

숫자 사이사이에 들어갈 기호를 모두 대입해보며 진행해야 한다. 일반적인 완전탐색으로는 구현하기 힘들고 재귀를 이용한 탐색을 사용해야 한다. 백트래킹 기법을 이용하여 앞서 대입한 연산자도 바꿀수 있게했다. public class Main { static int n; static int a[]; static int oper[]; static int max = Integer.MIN_VALUE; static int min = Integer.MAX_VALUE; public static void main(String[] args) { Scanner sc = new Scanner(System.in); n = sc.nextInt(); a = new int[n]; oper = new int[4]; for(int i=0;..

배열에 대해서 방문한 적이 없고 땅이라면 인접한 땅에 대해서 DFS 를 한다. DFS 한 컴포넌트의 개수를 세어주면 된다. public class Main { static int w; static int h; static int a[][]; static boolean visited[][]; public static void main(String[] args) { Scanner sc = new Scanner(System.in); while(true) { w = sc.nextInt(); h = sc.nextInt(); if(w == 0 && h == 0) break; a = new int[h][w]; visited = new boolean[h][w]; for(int i=0; i

그래프에 대해 공부해 보았다면 DFS 로 풀 수 있는 문제란걸 유추할 수 있다. 연결된 정보를 가지고 문제를 푼다 -> 그래프 문제 만든 그래프로 최단거리, 최소거리를 구해야 한다 -> BFS 그렇지 않다 -> DFS 네트워크 연결이 한방향으로만 되지는 않을것이고 별도의 언급도 없으니 양방향 그래프라고 볼 수 있다. 2차원 배열로 그래프를 만들어 노드마다 연결된 노드 번호를 매겨주고 카운트를 세어주면 된다. 노드 탐색을 할때 연결된 노드를 전부 탐색한 뒤 재귀호출 하는 방식으로 구성하고 싶어서 큐를 이용했다. public class Main { static int n; static int a[][]; static boolean visited[]; static Queue q = new LinkedList(..