본문 바로가기

백트래킹7

1987 : 알파벳 (C++) 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 백트래킹기법을 사용하여 푼 문제이다. 백트래킹을 사용했기 때문에 visit배열을 따로 사용하지 않았다. #include #include using namespace std; int map[20][20]; bool check[26]; int R, C; int result = 0; int dx[4] = {1, -1, 0, 0}; int dy[4] = {0, 0, 1, -1}; void dfs(int x, int y, int cnt) { for(int i = .. 2021. 2. 9.
[백준] 2580번 : 스도쿠(JAVA) https://www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루어진 정사각형 판 위에서 이뤄지는데, 게임 시작 전 몇 몇 칸에는 1부터 9까지의 숫자 중 하나가 쓰여 있다. 나머지 빈 칸을 채우는 방식은 다음과 같다. 각각의 가로줄과 세로줄에는 1부터 9까지의 숫자가 한 번씩만 나타나야 한다. 굵은 선으로 구분되어 있는 3 www.acmicpc.net 위의 문제는 BaekJoon Online Judge의 단계별로 풀어보기 중 15단계 백트래킹의 카테고리에 포함되어 있는 문제이다. impo.. 2020. 2. 25.
[백준] 9663번 : N-Queen(JAVA) https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 위의 문제는 BaekJoon Online Judge의 단계별로 풀어보기 중 13단계 백트래킹의 카테고리에 포함되어 있는 문제이다. 이 문제는 크기가 N * N인 체스판 위에 N개의 퀸을 서로 공격할 수 없게 놓는 문제이다. 체스판에서 퀸은 가로세로대각선을 모두 공격할 수 있는 최고의 말이다. visit_a과 visit_b는 바로 다음행의 각각 바로위의 대각선에 퀸을 놓지 않기 위해 선언한 배열이다. '자료구조와 .. 2019. 12. 9.
[백준] 15652번 : N과 M (4)(JAVA) https://www.acmicpc.net/problem/15652 15652번: N과 M (4) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해야 한다. www.acmicpc.net 위의 문제는 BaekJoon Online Judge의 단계별로 풀어보기 중 13단계 백트래킹의 카테고리에 포함되어 있는 문제이다. 이번 문제는 중복을 허용하면서 숫자의 순서가 비 내림차순인 순서여야 하는 문제이다. 이전의 문제들을 풀고나니 푸는데 어려움이 없던 문제이다. import java.util.Scanner; public class Question_15652 { static in.. 2019. 12. 6.
[백준] 15651번 N과 M (3)(JAVA) https://www.acmicpc.net/problem/15651 15651번: N과 M (3) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해야 한다. www.acmicpc.net 위의 문제는 BaekJoon Online Judge의 단계별로 풀어보기 중 13단계 백트래킹의 카테고리에 포함되어 있는 문제이다. 이전문제들에서는 숫자의 중복이 허용되지 않았다면 이번문제는 숫자의 중복이 허용되는 문제이다. 자바의 경우 System.out.print를 사용하면 시간초과가 난다. 그래서 처음 풀었을 때는 시간초과가 났었다. BufferedWriter를 사용했다. 숫자의 중.. 2019. 12. 4.
[백준] 15650번 : N과 M (2)(JAVA) https://www.acmicpc.net/problem/15650 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해야 한다. www.acmicpc.net 위의 문제는 BaekJoon Online Judge의 단계별로 풀어보기 중 13단계 백트래킹의 카테고리에 포함되어 있는 문제이다. 이전의 15649번 문제인 N과 M (1)의 문제와 비슷한 문제이다. (1)은 모든 경우를 출력하였다면, (2)는 오름차순의 경우에만 출력하는 문제이다. 나는 기존의 코드에서 다음 재귀를 호출하기 전 출력하려는 배열에 오름차순이 저장되어 있다면 다음을 호출하.. 2019. 12. 4.
[백준] 15649번 : N과 M (1)(JAVA) https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해야 한다. www.acmicpc.net 위의 문제는 BaekJoon Online Judge의 단계별로 풀어보기 중 13단계 백트래킹의 카테고리에 포함되어 있는 문제이다. 아직 나에게 있어 백트래킹은 어려운 알고리즘이라서 구글링을 통해 검색하고 코드를 보고 공부하여 문제를 해결하였다. 좀더 공부하고 쓰면서 단계를 이해하여야겠다. import java.util.Scanner; public class Question_15649 {.. 2019. 12. 4.