ote2010   3년 전

뭐가 틀렸는지 모르겠네요... 직접 입력바꿔봐도 맞는거같은데..ㅠㅠ


zlzmsrhak   3년 전

1. 39, 44번째 줄에서 i가 N을 넘어갈 수 있습니다.

2. 무슨 알고리즘으로 작성한 코드인지 모르겠지만, 백트래킹이라면 방법이 잘못되었습니다.

저 경우는, 전수조사를 하는 코드처럼 보이지만, 사실은 

1) 모든 첫 비숍의 위치 N^2에 대하여,

2) 행이 가장 작은, 같은 경우 열이 가장 작은 위치에 비숍을 하나씩 놓아보기

입니다. 이런 식으로 처리하면 모든 경우를 처리할 수 없습니다.

반례입니다.

ote2010   3년 전

저.. 무슨 말씀이신지 조금 더 구체적으로 설명해주시면 안될까요?ㅠㅠ

백트래킹을 공부하면서 푼 문제이긴 합니다..ㅠㅠ 코드 알아보시기 어려우신거같아서 주석도 달았습니다..ㅠㅠ

그리구 반례로 들어주신거는 출력이 3 아닌가요?? 지금 저 코드에서 3 잘 나오는데..ㅠㅠ 아 그리고 지적해주신 i는 바꿨습니다 감사합니다

zlzmsrhak   3년 전

1. 제가 깜박하고 0과 1을 반대로 써놨네요.. 반례 다시 드릴게요. 답은 4입니다.

2. 코드는 알아봤는데 코드가 구현하려는 것이 무엇인지 예상이 안되서 코드가 하는 일을 적어놓은 것입니다.

구현하려는 알고리즘이 무엇인지 설명하지 않으면 구체적인 답변을 얻을 수 없겠죠.

단순히 저 코드만 보면 그리디 알고리즘처럼 생겼습니다.

3. 백트래킹은 "전수조사"가 목적이기 때문에, 재귀를 호출한 후 상태를 초기화 해 주어야 합니다.

105번째 줄에서 초기화를 한 것 처럼, 65번째 줄에서 함수가 끝날 때, 시작부분에서 놓아둔 비숍을 물리는 작업을 해야 합니다.

아마 이렇게 구현하면 시간초과가 날 가능성이 꽤 높은데, 시간초과가 나오면 다시 질문하세요.

ote2010   3년 전

아.....제가 완전 잘못짰네요ㅠㅠㅠㅠ 자세히 설명해주시고 반례도 찾아주셔서 정말 감사드립니다ㅠㅠ 다시 더 공부해보고 모르는 게 있으면 질문 올릴께요!!
감사합니다

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