백트래킹
[백준] 15684 - 사다리 조작 (자바 Java)
[Gold III] 사다리 조작 - 15684 문제 링크 성능 요약 메모리: 298428 KB, 시간: 868 ms 분류 백트래킹(backtracking), 브루트포스 알고리즘(bruteforcing), 구현(implementation) 문제 설명 사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선이 같은 위치를 갖는다. 아래 그림은 N = 5, H = 6 인 경우의 그림이고, 가로선은 없다. 초록선은 세로선을 나타내고, 초록선과 점선이 교차하는 점은 가로선을 놓을 수 있는 점이다. 가로선은 인접한 두 세로선을 연결해야 한다. 단, 두 가로선이 연속하거나 서로 접하면..
[백준] 1987 - 알파벳 (자바 Java)
[Gold IV] 알파벳 - 1987 문제 링크 성능 요약 메모리: 12936 KB, 시간: 996 ms 분류 백트래킹(backtracking), 깊이 우선 탐색(dfs), 그래프 이론(graphs), 그래프 탐색(graph_traversal) 문제 설명 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다. 좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 프로..
[백준] 12100 - 2048 (Easy) (자바/Java)
문제 링크 성능 요약 메모리: 24332 KB, 시간: 348 ms 분류 백트래킹(backtracking), 브루트포스 알고리즘(bruteforcing), 구현(implementation), 시뮬레이션(simulation) 문제 설명 2048 게임은 4×4 크기의 보드에서 혼자 즐기는 재미있는 게임이다. 이 링크를 누르면 게임을 해볼 수 있다. 이 게임에서 한 번의 이동은 보드 위에 있는 전체 블록을 상하좌우 네 방향 중 하나로 이동시키는 것이다. 이때, 같은 값을 갖는 두 블록이 충돌하면 두 블록은 하나로 합쳐지게 된다. 한 번의 이동에서 이미 합쳐진 블록은 또 다른 블록과 다시 합쳐질 수 없다. (실제 게임에서는 이동을 한 번 할 때마다 블록이 추가되지만, 이 문제에서 블록이 추가되는 경우는 없다) ..
[백준] 1759 - 암호 만들기 (자바/Java)
문제 링크 성능 요약 메모리: 13036 KB, 시간: 120 ms 분류 백트래킹(backtracking), 브루트포스 알고리즘(bruteforcing), 조합론(combinatorics), 수학(math) 문제 설명 바로 어제 최백준 조교가 방 열쇠를 주머니에 넣은 채 깜빡하고 서울로 가 버리는 황당한 상황에 직면한 조교들은, 702호에 새로운 보안 시스템을 설치하기로 하였다. 이 보안 시스템은 열쇠가 아닌 암호로 동작하게 되어 있는 시스템이다. 암호는 서로 다른 L개의 알파벳 소문자들로 구성되며 최소 한 개의 모음(a, e, i, o, u)과 최소 두 개의 자음으로 구성되어 있다고 알려져 있다. 또한 정렬된 문자열을 선호하는 조교들의 성향으로 미루어 보아 암호를 이루는 알파벳이 암호에서 증가하는 순서..
[백준] 14888 - 연산자 끼워넣기 (자바/Java)
[Silver I] 연산자 끼워넣기 - 14888 문제 링크 성능 요약 메모리: 13276 KB, 시간: 120 ms 분류 백트래킹(backtracking), 브루트포스 알고리즘(bruteforcing) 문제 설명 N개의 수로 이루어진 수열 A1, A2, ..., AN이 주어진다. 또, 수와 수 사이에 끼워넣을 수 있는 N-1개의 연산자가 주어진다. 연산자는 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷)으로만 이루어져 있다. 우리는 수와 수 사이에 연산자를 하나씩 넣어서, 수식을 하나 만들 수 있다. 이때, 주어진 수의 순서를 바꾸면 안 된다. 예를 들어, 6개의 수로 이루어진 수열이 1, 2, 3, 4, 5, 6이고, 주어진 연산자가 덧셈(+) 2개, 뺄셈(-) 1개, 곱셈(×) 1개, 나눗셈(÷)..
[백준] 9663 - N-Queen (자바/Java)
문제 N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N이 주어진다. (1 ≤ N < 15) 출력 첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다. dfs를 활용해서 풀 수 있다는 건 쉽게 파악이 되는데 시간 초과와 메모리 초과때문에 오래 걸린 문제였다. 일단 처음에는 chess 배열에 queen을 하나씩 저장하면서 dfs로 깊이가 N이 될 때까지 검사하려고 하였다. r과 c를 이중 for문을 돌며 모두 검사하다 보니 row=0일 때 검사한 결과를 다시 row=1일 때도 추가하는 문제가 발생하였다. 그래서 dfs 함수에 row를 변수로 넣어주..
[백준] 15650 - N과 M (2) (자바/Java) 백트래킹 DFS 조합
문제 자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열 고른 수열은 오름차순이어야 한다. 입력 첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8) 출력 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해야 한다. 이전 문제와 달라진 점은 전의 문제가 순열이었다면 이번에는 조합을 구하는 경우이다. 조건에 수열이 오름차순이라는 것이 추가되었는데, 이는 즉 1 2 3 4만 허용되고, 1 2 4 3, 1 4 3 2 등은 허용되지 않는 것이니 중복을..
[백준] 15649 - N과 M (1) (자바/Java) 백트래킹 DFS
문제 자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열 입력 첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8) 출력 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해야 한다. 이 문제는 백트래킹을 활용한 문제이다. 그 중에서도 DFS를 활용하여 문제를 풀었다. 먼저 방문 여부를 체크할 check 배열을 만들고, 결과를 담을 result 배열을 만들었다. cnt가 0부터 시작해서 M이 될 때까지 dfs를 계속하는데, 방문되지 않은 노드를 ..