문제 링크: https://www.acmicpc.net/problem/7682 7682번: 틱택토 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 줄은 9개의 문자를 포함하며, 'X', 'O', '.' 중 하나이다. '.'은 빈칸을 의미하며, 9개의 문자는 게임판에서 제일 윗 줄 왼쪽부터의 순서이다. 입 www.acmicpc.net DFS, 순열, 백트랙킹 알고리즘 각 테스트 케이스에 대해서 해당 케이스가 가능한 틱택토 경우의 수인지 판단하는 방법은 9개의 위치에 토큰을 놓는 순열을 구하면 됩니다. 9개의 위치에 토큰을 놓는 순열을 구하면 경우의 수는 9! = 362880입니다 가능한 순열을 state[362880][3][3] 배열에 하나씩 저장하고 테스트 케이스가 이 배열 안에 존재하는 지만 판단..

문제 링크: https://www.acmicpc.net/problem/19236 19236번: 청소년 상어 첫째 줄부터 4개의 줄에 각 칸의 들어있는 물고기의 정보가 1번 행부터 순서대로 주어진다. 물고기의 정보는 두 정수 ai, bi로 이루어져 있고, ai는 물고기의 번호, bi는 방향을 의미한다. 방향 bi는 www.acmicpc.net 백 트랙킹 이 문제는 백트래킹을 할 때 상태 정보 백업 및 복원이 가장 핵심입니다. 상어를 1칸 이동, 2칸 이동, 3칸 이동시키고 각각에 대해서 재귀 호출할 때 재귀 호출 전에 백업, 호출 후 복원을 하면 되고, 물고기들이 이동하는 건 클래스로 좌표와 방향을 저장해 두고 1번부터 16번까지 단순히 움직이면 됩니다. 이때 주의할 점은 상어는 물고기가 있는 칸만 이동할..

문제 링크: https://www.acmicpc.net/problem/12094 12094번: 2048 (Hard) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 백트랙킹 https://www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 2048..

문제 링크: https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net DFS, 백트랙킹 DFS로 갈 수 있는 최장 거리를 구하면 되는데 방문한 좌표로 방문 체크를 하는게 아니라 알파벳 사용여부로 방문체크를 해야 된다. visited[26]; ->알파벳 'A' ~ 'Z' 각각에 'A'를 빼주면 0 ~ 25의 값에 대응시킬 수 있다 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 ..

문제 링크: https://www.acmicpc.net/problem/18809 18809번: Gaaaaaaaaaarden 첫째 줄에 정원의 행의 개수와 열의 개수를 나타내는 N(2 ≤ N ≤ 50)과 M(2 ≤ M ≤ 50), 그리고 초록색 배양액의 개수 G(1 ≤ G ≤ 5)와 빨간색 배양액의 개수 R(1 ≤ R ≤ 5)이 한 칸의 빈칸을 사이에 두 www.acmicpc.net 백트랙킹 1. 배양액을 뿌릴 수 있는 땅에 대해서 같은 것이 있는 순열(RRRGG...)을 구한다. 2. 뽑은 수열에 대해서 큐 두 개를 준비해서 빨간색 배양액, 초록색 배양액을 동시에 BFS를 진행한다. -> 큐에는 항상 같은 레벨(같은 초)의 좌표가 들어간다. -> BFS를 진행할 때 매 초마다 빨간색 배양액과 초록색 배양..

문제 링크: https://www.acmicpc.net/problem/1799 1799번: 비숍 첫째 줄에 체스판의 크기가 주어진다. 체스판의 크기는 10이하의 자연수이다. 둘째 줄부터 아래의 예와 같이 체스판의 각 칸에 비숍을 놓을 수 있는지 없는지에 대한 정보가 체스판 한 줄 단위로 www.acmicpc.net 백트랙킹 https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 이문제는 9663번 문제와 비슷하게 접근하면 되는데 핵심은 다음 세 가지입니다. 1. 체스..

문제 링크: https://www.acmicpc.net/problem/1941 1941번: 소문난 칠공주 총 25명의 여학생들로 이루어진 여학생반은 5×5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생이 두각을 나타내며 다른 학생들을 휘어잡기 시작 www.acmicpc.net 백트랙킹 5X5 격자에서 7자리를 뽑아서(2차원 배열에서 조합) BFS로 연결 여부 확인 + S의 개수가 4 이상인지 확인하면 됩니다. 2차원 배열 조합 for (int i = s; i

문제 링크: https://www.acmicpc.net/problem/16987 16987번: 계란으로 계란치기 원래 프로그래머의 기본 소양은 팔굽혀펴기를 단 한 개도 할 수 없는 것이라고 하지만 인범이는 3대 500을 넘기는 몇 안되는 프로그래머 중 한 명이다. 인범이는 BOJ에서 틀린 제출을 할 때마다 턱 www.acmicpc.net 가장 왼쪽의 계란을 든다. 손에 들고 있는 계란으로 깨지지 않은 다른 계란 중에서 하나를 친다. 단, 손에 든 계란이 깨졌거나 깨지지 않은 다른 계란이 없으면 치지 않고 넘어간다. 이후 손에 든 계란을 원래 자리에 내려놓고 3번 과정을 진행한다. 가장 최근에 든 계란의 한 칸 오른쪽 계란을 손에 들고 2번 과정을 다시 진행한다. 단, 가장 최근에 든 계란이 가장 오른쪽에..