반응형 백트래킹7 백준 1799번 비숍 - 스위프트(Swift) 풀이 + 그림 설명 1. 백트래킹으로 비숍을 하나씩 놓아본다. 2. 현재 비숍들이 놓인 상태를 대각선 비트 마스킹으로 표시한다. 3. 검은색 칸과 흰색 칸을 따로 생각해서 구한다. 1. 백트래킹으로 비숍을 하나씩 놓아본다. 비숍을 하나씩 놓아본다. 각 칸을 순차적으로 순회하면서 해당 칸에 비숍을 놓는 경우와 놓지 않는 경우를 다 해보면 된다. 다음칸으로 넘어갈 때는 비숍의 경로가 겹치면 안 되기 때문에 현재 체스판의 상황을 같이 넘겨주어야 한다. 2. 현재 비숍들이 놓인 상태를 대각선 비트 마스킹으로 표시한다. 현재 체스판 상태를 N*N짜리 배열로 넘겨주는 것은 비효율적이다. 어차피 비숍은 대각선으로만 이동할 수 있으므로, 대각선마다 비숍이 위치하는지 여부만 넘겨주자. 현재 칸이 속한 두 종류의 대각선을 모두 확인해서, 두.. 2022. 2. 6. 백준 2239번 스도쿠 - 스위프트(Swift) 풀이 1. 차례로 빈칸을 찾아 1-9중에 가능한 숫자를 전부 넣어본다. 2. 마지막 빈칸까지 다 채우면 전체 탐색을 종료한다. 1. 차례로 빈칸을 찾아 1-9중에 가능한 숫자를 전부 넣어본다. 결국 모든 빈칸을 다 채워야 하므로, 빈칸을 채울 순서를 정한 뒤 차례로 빈칸을 채워보면 되는 백트래킹 문제이다. 빈칸에 들어갈 수 있는 숫자 1-9 중에, 채울 수 있는 숫자들로만 채워본다. (만약 같은 행 또는 열 또는 블록에 같은 숫자가 있으면 채울 수 없다.) 만약 해가 여러 개라면 사전식으로 앞서는 것을 출력해야 하므로, 작은 수인 1부터 9까지 차례로 넣어준다. 해당 빈칸을 채웠으면, 다음 차례 칸을 채우는 함수를 또 재귀적으로 호출한다. 아래 코드에서는 각 칸에 row*9+col로 번호를 매겨 순서를 정했다.. 2022. 1. 27. 이전 1 2 다음 반응형
