Backtracking
-
[BOJ] 1987 알파벳PS/BOJ 2020. 7. 17. 17:00
https://www.acmicpc.net/problem/1987 1987번: 알파벳 문제 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 www.acmicpc.net 알고리즘: DFS, Backtracking 접근: 1. 경로 탐색 문제 2. 같은 알파뱃이 적힌 칸은 두 번 지날 수 없다 3. 최대한 몇 칸을 지날 수 있는가 -> 1, 3번 조건을 보면 이 문제가 DFS 문제라는 것을 알 수 있다. (경로를 탐색해가면서 최장경로 찾기) 이제 2번 조건만 해결해주면 된다. 2번은 조건은 알파뱃과 숫자를 하나씩 대응시켜 (A-0, B-1, C-2, ...,..
-
[BOJ] 1799 비숍PS/BOJ 2020. 7. 16. 19:01
https://www.acmicpc.net/problem/1799 1799번: 비숍 첫째 줄에 체스판의 크기가 주어진다. 체스판의 크기는 10이하의 자연수이다. 둘째 줄부터 아래의 예와 같이 체스판의 각 칸에 비숍을 놓을 수 있는지 없는지에 대한 정보가 체스판 한 줄 단위로 www.acmicpc.net 알고리즘: Backtracking (brute-force) 접근: N-queen 문제랑 비슷한 문제로 brute-force로 접근하였다. 이런 류의 문제는 항상 그렇듯 얼마나 가지치기를 잘하냐에 따라 정답이 갈린다. (오답의 대부분은 TLE 일 것이다.) 고로 비숍을 배치한다 했을 때, 왼쪽/오른쪽 대각선 모든 좌표를 일일히 확인하는 것은 상당히 비효율적이며 좀 더 효율적인 방식을 찾아야 한다. 그래서 각..