https://www.acmicpc.net/problem/4672풀이체스판이 주어졌을 때 놓을 수 있는 최대 룩 개수를 구하는 문제다. 체스판은 빈 칸은 '.', 벽은 'X'로 되어있다. 룩은 벽을 통과하여 이동할 수 없다. n-Queen 문제와 비슷하게 백트래킹을 사용하여 풀었다. 로직1. 체스판을 입력하면서 빈 칸의 수를 카운트한다. 빈 칸의 수는 답(최대 룩 개수)이 될 수 있는 최댓값이기 때문에, 추후 탐색할 때 이미 해당 값을 구한다면 탐색을 더 이상 하지 않는다.2. rook(0, 0, 0)을 호출한다. rook(int r, int c, int count)(r,c) 좌표에 룩을 놓을 수 있는지 검사한 후 놓을 수 있다면 rook(r, c+1, count+1)을 호출한다.해당 칸을 스킵하는 경우..

https://www.acmicpc.net/problem/9663문제대표적인 백트래킹 문제다.완전탐색/DFS와 비슷하지만, '정답이 될 수 없다면 다시 돌아오는 과정' = 가지치기를 한다.즉, 불필요한 경로는 끝까지 탐색하지 않는다. 백트래킹의 개념과 문제 모음 풀이import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.*;public class Main { static int n; static boolean[][] board; static int count = 0; public static void main(String[] args) throws ..

https://www.acmicpc.net/problem/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net 풀이 완전탐색으로 CCTV의 방향이 될 수 있는 모든 경우의 수를 구하여 그 중 사각지대가 최소인 경우의 크기를 구하였다. 완전탐색(재귀)로 모든 경우의 수를 구하므로 다음 변수들을 전역변수로 선언하였다. - 사무실 크기 n, m - 사무질 정보를 저장하는 rooms[n][m]을 생성 - 사각지대의 최소 크기를 저장하는 minUnwatchRoomCnt를 64로 초기화 - CCTV의 번호..

https://www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 풀이 DFS를 사용하여 스도쿠의 빈 칸에 모든 수를 집어넣고 각 경우마다 스도쿠가 될 수 있는지 체크한다. 로직 1. 스도쿠의 빈 칸 좌표를 ArrayList points에 넣는다. 2. sudoku(idx:0)을 호출한다. 이 때 idx는 points의 인덱스다. 3. points에서 좌표를 꺼내고, for문으로 1~9까지 해당 좌표에 들어갈 수 있는지 check() 함수를 통해 체크한다. 들어..

https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 풀이 말이 지날 수 있는 최대의 칸 수를 구하기 위해, DFS를 사용해서 모든 경우를 탐색해야 한다. 이 때 같은 알파벳이 적힌 칸을 두 번 지날 수 없으므로, 중복되는 알파벳이 있는지 체크하기 위해 map을 사용한다. 칸을 이동할 때마다 그 칸의 알파벳을 map의 key로 저장하고, 다음 칸으로 이동하기 전 map.containsKey() 메서드를 호출하여 다음 칸의 알파벳이 map에 있..

https://www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 풀이 문제를 보고 조합을 이용해야겠다는 생각이 들었다. 암호에는 알파벳을 중복하여 사용할 수 없고, 암호를 이루는 알파벳이 증가하는 순서로 배열되어야 한다. 즉, 입력받는 C개의 문자를 배열에 저장하여 알파벳 순으로 정렬하고, 배열 인덱스(0 ~ C-1)의 모든 조합의 경우의 수를 구하면, 가능성 있는 암호의 모든 경우를 구할 수 있다. 조합은 DFS로 구현한다. 조합을 구현하는 기본 틀은 다음과 같다..