반응형 비트마스킹12 백준 1799번 비숍 - 스위프트(Swift) 풀이 + 그림 설명 1. 백트래킹으로 비숍을 하나씩 놓아본다. 2. 현재 비숍들이 놓인 상태를 대각선 비트 마스킹으로 표시한다. 3. 검은색 칸과 흰색 칸을 따로 생각해서 구한다. 1. 백트래킹으로 비숍을 하나씩 놓아본다. 비숍을 하나씩 놓아본다. 각 칸을 순차적으로 순회하면서 해당 칸에 비숍을 놓는 경우와 놓지 않는 경우를 다 해보면 된다. 다음칸으로 넘어갈 때는 비숍의 경로가 겹치면 안 되기 때문에 현재 체스판의 상황을 같이 넘겨주어야 한다. 2. 현재 비숍들이 놓인 상태를 대각선 비트 마스킹으로 표시한다. 현재 체스판 상태를 N*N짜리 배열로 넘겨주는 것은 비효율적이다. 어차피 비숍은 대각선으로만 이동할 수 있으므로, 대각선마다 비숍이 위치하는지 여부만 넘겨주자. 현재 칸이 속한 두 종류의 대각선을 모두 확인해서, 두.. 2022. 2. 6. 백준 1007번 백터 매칭 - 스위프트(Swift) 풀이 1. 각 점을 위치 벡터로 생각한다. 2. 점 A에서 B로 가는 벡터는 (B 위치 벡터) - (A 위치 벡터)이다. 3. 절반을 역벡터로 만든 뒤 모든 벡터를 합치면 벡터 매칭에 있는 벡터의 합을 구할 수 있다. 1. 각 점을 위치 벡터로 생각한다. 먼저 각 점을 위치 벡터로 생각해줄 것이다. 2. 점 A에서 B로 가는 벡터는 (B 위치 벡터) - (A 위치 벡터)이다. 다음과 같은 성질을 이용할 것이다. 두 점 A, B를 골라 A→B 또는 B→A로 가도록 벡터로 잇는 작업은, 두 점 A, B를 고른 뒤 두 점으로 가는 위치 벡터 중 하나를 역벡터로 만드는 작업이라고 할 수 있다. 3. 절반을 역벡터로 만든 뒤 모든 벡터를 합치면 벡터 매칭에 있는 벡터의 합을 구할 수 있다. 결국 구해야 하는 것은 벡터.. 2022. 2. 4. 이전 1 2 3 다음 반응형
