목록2024/05/28 (1)

1일1알

백준 1799번 비숍 C++ (골드1)

https://www.acmicpc.net/problem/1799 대각선으로만 이동할 수 있는 비숍 말들을 영역이 겹치지 않게 배치할 수 있는 최대의 수를 구하는 문제이다.처음에 배치할 수 있는 영역은 제한되어있고, 배치를 못하는곳에 움직이는 것은 가능하다. 우선 직관적으로 백트래킹으로 접근하여 배치가 가능한 영역들을 저장하고 저장한 영역들에 대해 백트래킹을 돌려주었다.한번 배치한 영역은 4가지 대각선 방향에 다른 말이 배치할 수 없도록 표시를 해두고 저장해뒀다가, 돌아올때는 표시한 영역들을 다시 원상태로 돌려주었다. 하지만 역시 골드1이라그런지 이런 단순한 방법으로는 풀리지 않았고 시간초과가 났다. 계속 생각해봤는데도 마땅한 방법이 생각나지 않아서 질문 게시판을 한번 들어가봤는데 흑색과 백색으로 나누라..
알고리즘 2024. 5. 28. 11:46
이전 Prev 1 Next 다음