(python3)
1799번: 비숍
첫째 줄에 체스판의 크기가 주어진다. 체스판의 크기는 10이하의 자연수이다. 둘째 줄부터 아래의 예와 같이 체스판의 각 칸에 비숍을 놓을 수 있는지 없는지에 대한 정보가 체스판 한 줄 단위로
www.acmicpc.net
N-queen 의 추억
n퀸.. 유명한 알고리즘 문제죠 처음 이 문제를 마주쳤을 때 혼자서 풀어보겠다고 이틀을 머리 싸맸던 기억이 나네요..ㅋㅋㅋ 이후 다른 알고리즘 책을 읽으면서 명료한 풀이법을 알게 됐었습니다.
n-queen 의 기본 아이디어는 "우상향으로 같은 대각선의 경우 x+y 가 동일하다는것, 우하향으로 같은 대각선의 경우 x-y 가 동일하다는것" 입니다. 우상향, 우하향 대각선을 의미하는 배열을 각각 놓고 그 대각선에 이미 기물이 있다면 flag 를 1 로, 없다면 0 으로 설정하는 방식을 사용합니다. 이 방식을 취하면 (N*2-1) 칸짜리 배열 두개로 체스판 전체 정보를 가져가지 않고도 기물을 놓을 수 있는지 여부를 판단할 수 있습니다. 물론 체크하는 속도도 훨씬 빨라집니다.
서로 영향을 주지 않는 칸들 끼리는 재귀를 분리하자
일단 이 문제는 새로운 비숍을 놓을 수 있는지 여부를 엔퀸 방식으로 처리해줄 필요가 있습니다.
그리고 추가로, 체스판의 흰칸과 검은칸을 따로 분리해서 재귀 탐색을 해주어야합니다.
문제 조건의 맥시멈인 10x10 체스판을 생각해보겠습니다.
모든 경우의 수를 한번에 탐색하려면 $2^{100}$ 의 연산을 돌아야합니다. 그런데 비숍의 경우 대각선상에서만 서로 영향을 주고 받기 때문에 검은칸은 흰칸에 영향을 주지 못합니다. 그 반대도 마찬가지구요. 서로 영향을 주고받는 칸들끼리만 재귀를 돌리는게 훨씬 효율적입니다.
흰칸 위에 올라갈 수 있는 비숍의 최대 개수와 검은칸 위에 올라갈 수 있는 비숍의 최대 개수를 따로 구해서 더해주게 되면, 각각 50칸씩 확인하면 되기 때문에 $2^{50} + 2^{50}$ 으로 해결이 가능합니다.
시간복잡도
여러 블로그들에 $O(2^{N/2*N/2})$ 라고 적혀있었는데, 가로 세로가 각각 절반으로 주는게 아니라, 탐색하는 칸을 절반씩 쪼개는 것이라 제 생각엔 $O(2^{N*N/2})$ 가 맞는 것 같습니다.
일반적으로 백준 1초에 1억 연산이라 2^N 의 경우 1초에 N=20 까지 제한이라고 하는데.. 잘 모르겠습니다. 로컬에서 10x10 체스 보드로 time 을 측정하면 0.7초 가 찍히더라구요.
코드
import sys
import time
def solution(input) :
# 입력받기
N = int(input().strip())
MAP = []
for _ in range(N) :
MAP.append(list(map(int,input().split())))
# N-Queen 스타일로 새로운 비숍을 놓을 수 있는지 체크하기 위한 배열
RD = [0] * 20 # r+c (우상향 대각선)
LD = [0] * 20 # r-c+N (우하향 대각선)
global maxcnt
maxcnt = 0
def bt(r,c,cnt,wb) : # wb=0 : (0,0) 부터 시작하는 케이스 (검정) / wb=1 : (1,0) 부터 시작하는 케이스 (흰색)
global maxcnt
if r>=N : # 행을 끝까지 돈 경우
maxcnt = max(maxcnt,cnt)
return
if c+2 >= N : # 열의 끝에 도달했으면 다음 행으로 이동, 다음행 시작 컬럼은 wb로 맞춘다
nr=r+1
nc=(nr+wb)%2
else :
nr=r
nc=c+2
bt(nr,nc,cnt,wb) # 새 비숍을 안놓고 진행
if MAP[r][c] : # (r,c) 가 초기 맵 상 놓을 수 있는 곳 일때
if RD[r+c] or LD[r-c+N] : # 다른 비숍의 영향으로 놓을 수 없다면 끝
return
else : # 놓을 수 있다면 놓고 진행
RD[r+c] = 1
LD[r-c+N] = 1
bt(nr,nc,cnt+1,wb)
RD[r+c] = 0 # 빠져나올땐 다시 빈칸으로 바꿔놓기
LD[r-c+N] = 0
F = 0
bt(0,0,0,0) # 검정색 체크
F+=maxcnt
maxcnt = 0
bt(0,1,0,1) # 흰색 체크
F+=maxcnt
print(F)
input = sys.stdin.readline
solution(input)
my solved.ac :
solved.ac
알고리즘 문제해결 학습의 이정표 🚩 Baekjoon Online Judge 문제들의 난이도 및 티어 정보를 제공하는 사이트입니다.
solved.ac
'Algorithem > 백준 PS with code' 카테고리의 다른 글
백준 #21608 - [G5] 상어 초등학교 : 구현 (0) | 2023.06.05 |
---|---|
백준 #1987 - [G4] 알파벳 : 백트래킹, 시간초과 (0) | 2023.06.04 |
백준 #10989 - [B1] 수 정렬하기 : 계수정렬(counting sort) (0) | 2023.06.02 |
백준 #21610 - [G5] 마법사 상어와 비바라기 : 구현 (0) | 2023.06.01 |
백준 #13305 - [S3] 주유소 : 그리디 (0) | 2023.06.01 |
(python3)
1799번: 비숍
첫째 줄에 체스판의 크기가 주어진다. 체스판의 크기는 10이하의 자연수이다. 둘째 줄부터 아래의 예와 같이 체스판의 각 칸에 비숍을 놓을 수 있는지 없는지에 대한 정보가 체스판 한 줄 단위로
www.acmicpc.net
N-queen 의 추억
n퀸.. 유명한 알고리즘 문제죠 처음 이 문제를 마주쳤을 때 혼자서 풀어보겠다고 이틀을 머리 싸맸던 기억이 나네요..ㅋㅋㅋ 이후 다른 알고리즘 책을 읽으면서 명료한 풀이법을 알게 됐었습니다.
n-queen 의 기본 아이디어는 "우상향으로 같은 대각선의 경우 x+y 가 동일하다는것, 우하향으로 같은 대각선의 경우 x-y 가 동일하다는것" 입니다. 우상향, 우하향 대각선을 의미하는 배열을 각각 놓고 그 대각선에 이미 기물이 있다면 flag 를 1 로, 없다면 0 으로 설정하는 방식을 사용합니다. 이 방식을 취하면 (N*2-1) 칸짜리 배열 두개로 체스판 전체 정보를 가져가지 않고도 기물을 놓을 수 있는지 여부를 판단할 수 있습니다. 물론 체크하는 속도도 훨씬 빨라집니다.
서로 영향을 주지 않는 칸들 끼리는 재귀를 분리하자
일단 이 문제는 새로운 비숍을 놓을 수 있는지 여부를 엔퀸 방식으로 처리해줄 필요가 있습니다.
그리고 추가로, 체스판의 흰칸과 검은칸을 따로 분리해서 재귀 탐색을 해주어야합니다.
문제 조건의 맥시멈인 10x10 체스판을 생각해보겠습니다.
모든 경우의 수를 한번에 탐색하려면
흰칸 위에 올라갈 수 있는 비숍의 최대 개수와 검은칸 위에 올라갈 수 있는 비숍의 최대 개수를 따로 구해서 더해주게 되면, 각각 50칸씩 확인하면 되기 때문에
시간복잡도
여러 블로그들에
일반적으로 백준 1초에 1억 연산이라 2^N 의 경우 1초에 N=20 까지 제한이라고 하는데.. 잘 모르겠습니다. 로컬에서 10x10 체스 보드로 time 을 측정하면 0.7초 가 찍히더라구요.
코드
import sys
import time
def solution(input) :
# 입력받기
N = int(input().strip())
MAP = []
for _ in range(N) :
MAP.append(list(map(int,input().split())))
# N-Queen 스타일로 새로운 비숍을 놓을 수 있는지 체크하기 위한 배열
RD = [0] * 20 # r+c (우상향 대각선)
LD = [0] * 20 # r-c+N (우하향 대각선)
global maxcnt
maxcnt = 0
def bt(r,c,cnt,wb) : # wb=0 : (0,0) 부터 시작하는 케이스 (검정) / wb=1 : (1,0) 부터 시작하는 케이스 (흰색)
global maxcnt
if r>=N : # 행을 끝까지 돈 경우
maxcnt = max(maxcnt,cnt)
return
if c+2 >= N : # 열의 끝에 도달했으면 다음 행으로 이동, 다음행 시작 컬럼은 wb로 맞춘다
nr=r+1
nc=(nr+wb)%2
else :
nr=r
nc=c+2
bt(nr,nc,cnt,wb) # 새 비숍을 안놓고 진행
if MAP[r][c] : # (r,c) 가 초기 맵 상 놓을 수 있는 곳 일때
if RD[r+c] or LD[r-c+N] : # 다른 비숍의 영향으로 놓을 수 없다면 끝
return
else : # 놓을 수 있다면 놓고 진행
RD[r+c] = 1
LD[r-c+N] = 1
bt(nr,nc,cnt+1,wb)
RD[r+c] = 0 # 빠져나올땐 다시 빈칸으로 바꿔놓기
LD[r-c+N] = 0
F = 0
bt(0,0,0,0) # 검정색 체크
F+=maxcnt
maxcnt = 0
bt(0,1,0,1) # 흰색 체크
F+=maxcnt
print(F)
input = sys.stdin.readline
solution(input)
my solved.ac :
solved.ac
알고리즘 문제해결 학습의 이정표 🚩 Baekjoon Online Judge 문제들의 난이도 및 티어 정보를 제공하는 사이트입니다.
solved.ac
'Algorithem > 백준 PS with code' 카테고리의 다른 글
백준 #21608 - [G5] 상어 초등학교 : 구현 (0) | 2023.06.05 |
---|---|
백준 #1987 - [G4] 알파벳 : 백트래킹, 시간초과 (0) | 2023.06.04 |
백준 #10989 - [B1] 수 정렬하기 : 계수정렬(counting sort) (0) | 2023.06.02 |
백준 #21610 - [G5] 마법사 상어와 비바라기 : 구현 (0) | 2023.06.01 |
백준 #13305 - [S3] 주유소 : 그리디 (0) | 2023.06.01 |