백트래킹

[백준] 17136. 색종이 붙이기 (Java)

문제 17136번: 색종이 붙이기 과 같이 정사각형 모양을 한 다섯 종류의 색종이가 있다. 색종이의 크기는 1×1, 2×2, 3×3, 4×4, 5×5로 총 다섯 종류가 있으며, 각 종류의 색종이는 5개씩 가지고 있다. 색종이를 크 www.acmicpc.net 알고리즘 브루트포스, 백트래킹 풀이 그리디 문제로 보일 수 있으나 모든 경우의 수를 탐색해야하는 완전 탐색 + 백트래킹 문제이다. (0, 0) 부터 (9, 9) 까지 각 좌표마다 각 색종이를 붙일 수 있다면 붙이고, 모든 1에 색종이를 붙였을 때 색종이 개수를 최솟값과 비교해 갱신하면 된다. 1. 좌표: (0, 0) 부터 (9, 9) 까지 2. 색종이 크기: 5 부터 1 까지 3. 해당 크기의 색종이가 남아있다면 4. 해당 좌표에 해당 크기의 색종이..

[백준] 2239. 스도쿠 (Java)

문제 2239번: 스도쿠 스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다 www.acmicpc.net 알고리즘 구현, 백트래킹 풀이 앞 쪽에 있는 0부터 1~9 중 가능한 수로 채워나가며 모든 경우의 수를 따져 해결한다. 답이 여러개 있다면 사전순으로 앞서는 것을 출력하라는 조건이 있기 때문에 1부터 9의 오름차순 순서로 값을 넣었을 때 가장 처음 성공하는 경우가 사전순으로 가장 앞서는 경우이다. 답이 없는 입력은 주어지지 않으므로 입력에서 0의 개수를 세고, 해당 좌표를 리스트에 저장한다. 재귀 호출 함수 안에서는 리스트의 앞에 있는 좌표부터 1~9..

[SWEA] 5656. [모의 SW 역량테스트] 벽돌 깨기 (Java)

문제 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 알고리즘 구현, 시뮬레이션, 백트래킹 풀이 1~W열까지 각 열에 구슬을 쏘는 경우라고 가정하여 구슬 쏘기를 진행하고, 해당 결과를 바탕으로 재귀를 돌려 1~W까지 N번 구슬을 쏘는 모든 경우를 탐색한다. 각 열마다 가장 위에 있는 벽돌의 index를 관리할 배열을 생성한다. 배열을 -1로 초기화해 벽돌이 없는 라인을 구분한다. 1~W열까지 각 열에 구슬을 쏘는 경우라고 가정하여 구슬을 쏜다. i열에 구슬 쏘기 1. 만약 i열에 벽돌이 없다면 구슬을 쏴도 의미가 없으므로 다음 열로 넘어간다. 2. i열에 벽돌이 있다면 맨 위의 벽돌을 깨고, 해당 벽돌의 정보(..

[백준] 19236. 청소년 상어 (Java)

문제 19236번: 청소년 상어 첫째 줄부터 4개의 줄에 각 칸의 들어있는 물고기의 정보가 1번 행부터 순서대로 주어진다. 물고기의 정보는 두 정수 ai, bi로 이루어져 있고, ai는 물고기의 번호, bi는 방향을 의미한다. 방향 bi는 www.acmicpc.net 알고리즘 구현, 시뮬레이션, 백트래킹 풀이 각 칸의 물고기 번호를 저장할 2차원 배열과 물고기 번호에 해당하는 물고기들의 정보(좌표, 번호, 방향, 생존 여부)를 담을 1차원 배열을 선언한다. board = new int[4][4]; fishList = new Fish[17]; fishList 배열을 통해 각 번호의 물고기가 어디 있는지 바로 접근할 수 있다. 큰 틀은 다음과 같다. 1. (0,0) 의 물고기를 잡아먹고, [상어의 좌표, 먹..

[백준] 12100. 2048 (Easy) (Java)

🔒 문제 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 🔑 알고리즘 깊이우선탐색(DFS), 브루트포스, 백트래킹 💡 풀이 전체 블럭을 상하좌우 네 방향으로 이동할 수 있고, 최대 5번 이동하므로 5번 이동하는 전체 경우의 수는 45 = 1024 가지로 많지 않다. 따라서 DFS를 통해 네 방향으로 이동하면서 5번 이동했을 때 최댓값을 갱신해주는 식으로 문제를 해결하였다. 네 방향 중 한 방향으로 이동을 수행하는데 한 번의 이동은 배열의 각 원소 모두 해당하는 방향의 이동 가능한 끝..