sujae03   2년 전

시간초과 때문에 질문드립니다.

제가 구현한 알고리즘은 다음과 같습니다.

1. Dir이라는 배열에 비숍이 갈 수 있는 길 ('1'인 경우)  저장해둡니다.

2. 갈 수 있는 길 (x,y) 좌표가 주어지면 대각선을 모두 체크하여 비숍이 놓일 수 있는지 체크합니다.

3. 만약 놓일 수 있다면 map에 '2'라고 비숍을 체크한 후 재귀를 통해 다음 갈 수 있는길을 똑같이 반복하며 놓일때마다 Cnt를 증가시킵니다.

   만약 놓일 수 없다면, 다음 갈 수 있는 길에서 똑같이 2번부터 수행합니다. 


하지만, 시간초과가 납니다 ㅠㅠ

시간초과를 줄일 수 있는 방법이 없을까요 ?

sgchoi5   2년 전

탐색 횟수를 줄일 수 있어야 하는데요. 그래서, 분류가 백트래킹이겠지요..
KOI 문제는 설명이 제공이 되니 한 번 분석해보시길..

sujae03   2년 전

답변 감사합니다,,

백트래킹이라는게,

1->2->3->4->5 검사하고 5에서 promising 하지 않으면 4로 back해서 그 다음 6을 검사하는 것이지 않나요 ???


저는 제가 백트래킹으로 구현한 줄 알았는데,

혹시 제 코드는 백트래킹이 아닌건가요 ???


P.S) 아 해당 비숍 문제는 위의 코드에서 흰 영역 / 검은 영역을 구분하여 해결하였습니다!

kioio5   2년 전

@sujae03

코드를 다 보진 않았는데..

백트래킹 하신건 맞아요

근데 이 문제는 일반적으로

백트래킹하면 시간초과 나요

체스판에는 흰판과 검은판이 있습니다.

비숍은 대각선으로만 이동하기 때문에 이동할 수 있는 곳은 같은 색으로만 이동할 수 있어요.

그래서 두 공간을 나눠서 생각한다면 전부 돌지 않고 반반 나눠서 돌 수 있겠네용

힌트는 대각선입니다.(다른 방법도 있을 수 있지만 저는 대각선으로 풀었습니당)

sujae03   2년 전

@kioio5


답변 감사합니다 ^^

해결했습니다!

댓글을 작성하려면 로그인해야 합니다.