백트래킹 (1) 썸네일형 리스트형 [BOJ 1799, 약간 어려움] 비숍 (C++) 개인적인 난이도 약간 어려움 실패한 풀이) 체스판에서 대각선을 체크하면서 말을 놓는 백트래킹의 구현은 그렇게 어렵지 않으나, 그냥 백트래킹하면 시간초과가 나게 되는 문제이다. 약간의 아이디어로 시간복잡도를 크게 줄일 수 있다. 안되는 이유 최악의 경우, 10*10 의 배열의 모든 칸에 비숍을 배치할 수 있다 검사할 칸의 개수 100개 -> 백트래킹 없이 완전탐색할 경우 2^100~=1e30 대략 1e22초 소요 백트래킹으로 탐색하며 비숍을 배치할 수 있는 위치에만 비숍을 배치한다고 해도 시간초과가 난다. 그 이유는 이러하다. 10*10 크기의 2차원 배열의 경우 20+20 개의 대각선을 그릴 수 있다. 인정?? 인정~ 비숍을 어느 한 위치에 놓을때마다 우상향 방향 대각선 1개와 좌상향 방향 대각선 1개에.. 이전 1 다음
