[일반] 백준 비숍 (백트래킹) 문제 시간 초과 질문

일단 자바를 C++ 코드로 바꾸고, promising은 시간복잡도 엄청 줄일수 있고 그런건 없을걸

시아닌(kimjg1119) 2018-08-29 21:11

만약 N-Queen 문제에서 같은 행/열에는 더이상 말을 놓지 않는것처럼 각 대각선에 번호를 붙여 관리한다면 속도가 훨씬 빨라질 수 있을 것

시아닌(kimjg1119) 2018-08-29 21:13

이거 이분매칭 아님? 백트래킹으로도 풀리나

ㅎㅎㅎㅎㅎ(182.224) 2018-08-29 21:28

자바가 느려서 못 풀 수도 잇을거 같은데. 확실하게 풀려면 이분매칭으로 풀면 됨. 종만북에 아마 똑같은 문제 있던거 같음

ㅎㅎㅎㅎㅎ(182.224) 2018-08-29 21:36

시아닌/ 대각선으로 푸는 거 맞네. 이러면 시간복잡도 오져서 c든 뭐든 다 안풀림

익명(110.11) 2018-08-29 21:40

ㅎㅎㅎㅎㅎ/ 이분 매칭은 내가 모르는 거네 ㄷㄷ 일단 백트래킹 익히고 익혀야지

익명(110.11) 2018-08-29 21:41

이분매칭은 한참 뒤로 미뤄. 그건 꽤 어려운 알고리즘임

시아닌(kimjg1119) 2018-08-29 23:08

ㄴ 흑 ㅠㅠ 빨리 고수되고프다

익명(110.11) 2018-08-30 01:15

비숍2는 이분매칭 맞는데 저거는 백트래킹맞음

하루룽(ailedear) 2018-08-30 07:24

체스판 생각해보면 흰칸에 있는 비숍은 검은칸으로 못가고 검은칸 비숍은 흰칸으로 못가니까

하루룽(ailedear) 2018-08-30 07:26

체스판을 색깔로 분리하고 백트래킹 2번돌리면 됨

하루룽(ailedear) 2018-08-30 07:27

댓글 11