기맹기 개발 블로그

BOJ 1987 알파벳 난이도 : 골드 4 https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 전략 주어진 조건을 만족하도록 DFS로 탐색하면서 가장 많이 이동한 칸을 저장하면 된다. 시행착오 간단한 문제로 시행착오는 없었다. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { stati..

BOJ 1799 비숍 난이도 : 골드 1 https://www.acmicpc.net/problem/1799 1799번: 비숍 첫째 줄에 체스판의 크기가 주어진다. 체스판의 크기는 10이하의 자연수이다. 둘째 줄부터 아래의 예와 같이 체스판의 각 칸에 비숍을 놓을 수 있는지 없는지에 대한 정보가 체스판 한 줄 단위로 www.acmicpc.net 전략 N-Queen를 백트래킹으로 풀 때와 유사하지만 다음 조건들이 다르다. 1. 놓을 수 없는 위치가 존재한다는 점 2. 놓을 수 있는 비숍의 최대 개수를 구해야한다는 점 3. 비숍은 자신이 속한 흑/백 칸이 아닌 곳으로는 이동할 수 없다는 점 흑색/백색 칸을 따로 dfs로 진행하면서 더 이상 비숍을 놓을 수 없는 경우에는 백트래킹하고, 놓을 수 있는 경우에는 비..

BOJ 2239 스도쿠 난이도 : 골드 4 https://www.acmicpc.net/problem/2239 2239번: 스도쿠 스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다 www.acmicpc.net 전략 간단한 백트래킹 문제로 예전에 c++로 한번 풀었던 적이 있다. (BOJ 2580) 재귀에 너무 익숙해져있는 것 같아서 이번에는 스택으로 구현해보고자 풀어보았다. 시행착오 재귀로는 정적 배열을 수정하면서 간단하게 백트래킹을 구현할 수 있었다. 스택으로 하려니까 실패했을 때 이전 상태로 돌리는 것을 어떻게 처리할지 고민을 많이 했다. 따라서 cl..