와드의 블로그

문제크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제입니다. 체스에서 퀸은 상하좌우, 그리고 대각선 8방향으로 거리 제한 없이 이동할 수 있습니다. 즉, 어떤 퀸을 놓았을 때 같은 행, 같은 열, 같은 대각선 상에는 다른 퀸을 놓을 수 없습니다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하는 문제입니다.입력: 첫째 줄에 N이 주어집니다. (1 ≤ N 출력: 첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력합니다.링크: https://www.acmicpc.net/problem/9663풀이: 1차원 배열을 활용한 상태 압축과 백트래킹2차원 배열(N x N)을 사용하여 체스판을 모사하는 대신, 1차원 배열만으로 퀸의 위치를 기록하여 공간 복잡도와..

문제N x M 크기의 2차원 맵에서 시작점(y1, x1)부터 도착점(y2, x2)까지 이동하려고 합니다. 맵의 각 칸은 빈 칸('0') 또는 벽으로 이루어져 있습니다. 빈 칸으로 이동할 때는 비용이 들지 않지만(가중치 0), 벽을 부수고 이동할 때는 1의 비용이 발생합니다(가중치 1). 상하좌우로 이동할 수 있을 때, 시작점에서 도착점까지 가기 위해 부숴야 하는 벽의 최소 개수(최소 이동 비용)를 구하는 프로그램을 작성하는 문제입니다.입력: 맵의 세로 길이 n, 가로 길이 m, 시작점 좌표 y1, x1, 도착점 좌표 y2, x2, 그리고 맵의 상태 배열출력: 도착점까지 이동하기 위해 부숴야 하는 벽의 최소 개수링크: https://www.acmicpc.net/problem/14497풀이 1: 일반 Que..