백트랙킹 (4) 썸네일형 리스트형 [백준] 2580 스도쿠 (JAVA) https://www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 풀이 문제 자체가 어렵지는 않으나 풀이방법에 대해서 조금 고민을 하여 푼 문제이다. 스도쿠의 룰은 잘 알다시피 가로세로 그리고 3*3이 되어있는 칸에서 중복을 허용하지 않는 선에서 수를 채워넣는 것이다. 그리하여 나는 81칸 전부를 차례대로 순회하며 만약 빈칸이 있다면 해당 칸에 들어갈수 있는 수를 찾은뒤 arr에 집어넣고 재귀적으로 호출해 나가며 풀이를 진행했다. 여기서 살짝 헷갈릴는 점은 적정.. [백준] 9663 N-Queen (JAVA) 풀이 위의 문제는 백트랙킹의 기초적인 문제라고 할수있겠다. 이 문제를 접하게 된 경로는 solved에서 문제를 풀다 백트랙킹 문제를 맞닥뜨려 풀려고 하였으나 관련문제를 풀어본적이 없어 풀지를 못했다. 이러한 내 자신에거 실망을 하여 백트랙킹의 기초문제를 풀려고 찾아보았고 가장 기초적인 문제를 찾아서 풀었다. 문제는 크기가 n x n인 체스판에서 퀸을 몇개나 놓을수 있냐는 문제이다. 이러한 방식은 마지 스택을 이용한 미로찾기 처럼 하면되는데 미로찾기에서는 이차원의 배열을 만들어 사용했다면 여기서는 1차원의 배열을 이용해 열을 index값으로, 행을 원소값으로 생각하여 풀면 된다. 자세한것은 아래의 코드를 보면 될듯하다. 코드 import java.util.Scanner; class Main{ public .. [백준] 1182 부분수열의 합 (JAVA) 풀이 살짝 변칙적인 백트랙킹 인듯하다. 이문제에서는 for문이 필요하지 않다. 이해는 코드를 보면 갈것이다. 백트랙킹 문제를 더 풀어봐야 할것 같다. package com.company; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; class Main { static int N; static int S; static int count=0; static int Sum; static int[] Num; public static void main(String[] args) throws IOException { BufferedRea.. [백준] 6603 로또 (JAVA) https://www.acmicpc.net/problem/6603 위의 문제는 DFS를 이용한 백트랙킹으로 풀수있다. 처음에는 문제를 계속 풀려고 해도 풀리지가 않아서 타 블로그의 글을 보았다. 그럼에도 잘 이해가 가지않아서 혼자 연습장에 끄적거리보기도 하고 유튜브에 강의를 찾아보기도 하였다. 그러던 중 정말 크게 도움이 된 강의의 주소를 올려놓겠다. https://www.youtube.com/watch?v=Ar40zcPoKEI - 코드없는 프로그래밍님의 강의이다. 아래의 코드를 통해서 내가 몰랐던것들과 새로 이해한것에 대해서 설명을 하겠다. 전역으로는 ary(원소들의 집합), k(집합의 크기), skip(현재 선택한 원소들에 대해서 나타내는 배열)과 출력을 할때 쓰일BufferedWriter를 선언했다.. 이전 1 다음
