state는 3개인가요? x좌표, y좌표, 검은 녀석을 흰 녀석으로 바꾼 횟수.

그런데, 잘 봅시다. 검은 녀석을 흰 녀석으로 바꾼 횟수 >= n+m이고

n+m회 바꾸면 시작점에서 끝점까지 갈 수 있음이 보장됩니다. 만약에 visit[black_to_white][x][y] 이렇게 두었다면..

시간 복잡도는 (n+m)*n*m이 되겠네요.

Question

그러면, 더 좋은 방법이 없을까요? 

Hint. 검은 녀석에 들어왔을 때, cost가 1이고, 흰 녀석에 들어갔을 때 cost를 0으로 set 하면 어떨까요?

먼저, 답이 늦어 죄송합니다.. ㅠ 메리 크리스마스~^^ (보내세요)

으흠, 그렇군요. 어차피 n+n만큼 뒤집으면 최악의 경우의 최솟값이군요.

그래서 visit 배열을 visit[n+n][n][n]으로 놓는다고하면

공간 복잡도는 2 * n^3인거고... 음, 시간 복잡도도 2 * n^3 인거군요? (맞나요?)

n 최대가 50이니께 0.25 백만 번이면, 1초 충분하네요

Answer Try

음, 힌트를 먼저 읽으면

맵을 2차원 배열에 입력 받을 때 검은 방이면 1로 놓고 흰방이면 0으로 놓는다는 걸까요?

그러면 방문할 때 맵의 방문하는 칸 값을

이 번에 큐에서 뺀 친구의 방문값(지금까지 바꾼 방의 수)에 그대로 더해서

다시 큐에 넣어 줄 수 있을 것 같습니다.

조건문 써서 검은 칸인지 흰 칸인지 비교를 안해도 되니까

작성하기도 더 편하고 더 빨라질 것 같습니다 (이게 맞나여?)

이상, 하수 올림