thinker99   1년 전

흑백?같은거는 제가 감자라서 이해가 안가고 ㅠㅠ.. 우직하게 백트래킹으로 풀었습니다

일단 N-Queen 문제를 먼저 설명하는 것이 맞겠습니다

https://www.acmicpc.net/proble...

N-Queen 문제는 행, 열, 대각선(y=x꼴), 대각선(y=-x꼴)의 네 가지를 확인해야합니다

처음의 시도때는 m*m칸의 체스칸에서 퀸이 놓이지 않은 칸 전부에 대해 백트랙 전개를 하여, 네 가지 이동방향을 전부 if문으로 확인하게 만들었습니다

이러다보니 예컨데 {(0,0), (0,1), (0,2)}와 같은 불필요한 경우도 전부 확인하게 되고, 미친 시간복잡도의 디지털 쓰레기가 나왔습니다


N-Queen 문제를 시간 안에 풀려면 불필요한 확인을 백트랙 안에서 녹여버려야합니다

퀸의 네 방향 이동경로중 행과 열은 백트랙 함수 안에서 녹일수가 있습니다

퀸은 무조건 한 행에 하나만 있어야 하니, 놓을 수 있는(이 문제로 치면 1로 입력된) 모든 칸을 확인 할 것이 아닌

한 행에 퀸을 놓으면 체스판 다음 행으로 백트랙을 전개한다는거죠 (따라서 백트랙의 매개변수는 lv같은게 아닌 row가 되어야 합니다)

열은 checkedCol과 같은 bool 배열을 사용해서, 해당 열이 아직 사용되지 않은 경우만 백트랙을 전개하고요

같은 행, 열에 퀸을 또 넣으면 무의미한 백트랙 분기가 생기니까요


비숍 문제를 처음 볼 때 생각이

"N-Queen 문제에서 행열이 빠졌네? 그러면 행열 확인 코드 거르고 대각선만 확인하면 되는거 아냐?? 플레인데 짱쉽네????"

참 무식하면 용감하다고 이런 생각으로 코드를 재활용해서 풀었다가... 바로 시간초과가 났습니다

N-Queen을 풀었던 코드는 대각선 확인이 그렇게 효율적이지가 못했거든요

계속 고민하다 문득 떠오른 생각이, N-Queen 풀었던 때 처럼 불필요한건 녹여버린다는 아이디어입니다


체스판을 시계방향으로 45도 돌리면, 비숍 문제가 아닌 룩 문제가 되어버립니다

(룩은 행, 열 방향으로 무제한의 이동이 가능)

사진으로 이해하는게 빠르겠습니다

preview

m=3일 때, 3*3짜리 체스판을 시계방향으로 45도 돌린 모습입니다 <- 이를 새로운 체스판이라 하겠습니다

새로운 체스판은 5*5 크기이고, 한 변의 길이는 2*m - 1입니다 <- 이를 lim이라 하겠습니다

그러면 (0,0) -> (0,2), (1, 2) -> (3, 3)과 같이 되겠죠

preview

문제에서 예시로 준 테케는 이렇게 바뀝니다

좌표 변환을 일반화 시킨다면

새로운 r -> r + c

새로운 c -> ( (m - 1) - r ) + c

기존 체스판의 좌표를 새로운 체스판의 좌표로 변환해주는 함수를 하나 만들어주시면 좋습니다


이렇게 생각을 하게되면 기존 체스판에서는 대각선 이동을 했던 비숍이 새로운 돌린 체스판에서는 상하좌우 이동을 하는 룩이 됩니다

행, 열 확인은 N-Queen 문제도 백트랙에서 녹여버렸죠? 비숍 문제에서도 똑같이 녹여버립니다

한 행에 한 룩(이전에는 비숍)이 있어야 하고, 한 열 역시나 마찬가지입니다

백트랙의 매개변수가 row라면 어디까지 전개해야 할까요? 당연하게도 새로운 체스판의 한 변의 길이인 lim만큼 전개하면 됩니다

정답은 매 백트랙마다 갱신해 주시면 되고요


여기까지 완성하고 실행해보면 한 가지 문제가 생깁니다

5

0 0 0 0 0

0 1 0 1 0

1 0 0 0 1

0 1 0 1 0

0 0 0 0 0

이 입력의 정답은 3인데, 0이 출력됩니다

왜인지는 체스판을 돌려본 뒤 곰곰히 생각해보시면 답이 나올겁니다 (힌트 : 백트랙의 생각치 못한 분기에 있습니다)


이 돌린다는 아이디어가 떠오르지 않는다면 어려운데, 떠올린다면 개인적으로는 N-Queen보다 쉬웠던 것 같습니다

sunwoo0608   1년 전

저는 이렇게 했는데도 시간초과...

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