p0her

백 트래킹 단골 문제다. 퀸이 갈 수 있는 좌표를 잘 표시하는게 관건인데, 현재 퀸의 좌표를 (x, y) 라고 하자.

그럼 현재 좌표에서 아래 대각선에 퀸이 존재하는지 알아보려면 x+y가 같으면 된다. (기울기가 -1)

그럼 반대로 위 대각선에 퀸이 존재하는지 알아보려면 x-y가 같으면 된다. (기울기가 1)

이런식으로 위 대각선, 아래 대각선, 행에 대한 bool 변수를 두고 체크해가면서 백트래킹 해주면 된다. 기본적인 백트래킹 방법은 좋은 강의가 많으니 그걸 참고하면 되겠다..

미로탐색 (2178번) + 이동 단위 좌표 설정이다. 그림을 보면서 x, y가 어떻게 움직이는지 관찰하고 배열로 만들어주면 편하다.

const int dx[] = {-2, -2, -1, -1, 1, 1, 2, 2};
const int dy[] = {-1, 1, 2, -2, 2, -2, 1, -1};

이전 토마토 시리즈 (7576, 7569) 문제들의 뇌절 버전이다. 11차원에서 BFS를 수행하면 되는데, 어렵게 생각하지 말고 이전 문제들에서 dx, dy, dz 들을 잘 세팅해서 푼 것 처럼 이 문제도 각 좌표에 대한 이동 경로를 잘 구현해주면 쉽게 풀린다.

const int dm[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 1};
const int dn[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 1, 0, 0};
const int dO[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 1, 0, 0, 0, 0};
const int dp[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 1, 0, 0, 0, 0, 0, 0};
const int dq[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 1, 0, 0, 0, 0, 0, 0, 0, 0};
const int dr[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
const int ds[] = {0, 0, 0, 0, 0, 0, 0, 0, -1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
const int dt[] = {0, 0, 0, 0, 0, 0, -1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
const int du[] = {0, 0, 0, 0, -1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
const int dv[] = {0, 0, -1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
const int dw[] = {-1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};

이전 토마토 문제도 그렇고 이런 좌표를 설정해놓는 문제는 규칙이 존재하기 때문에 쉽게 생각할 수 있다. 좌표 실수를 조심하자.

백준에 똑같은 명의 7576번 문제 (토마토) 가 있는데 이 문제는 7576번의 3차원 버전의 문제다. 즉 7576번에선 이동하는 좌표를 2개로 놓고 풀수 있지만, 이 문제에선 3차원으로 접근 해야하기 때문에 상, 하, 좌, 우, 위, 아래를 모두 따져야한다. 해당 좌표를 잘 잡을 수 있으면 문제는 2차원 버전과 크게 다르지 않다.

const int dy[] = {0, 0, -1, 1, 0, 0};
const int dx[] = {-1, 1, 0, 0, 0, 0};
const int dz[] = {0, 0, 0, 0, -1, 1};

본인의 경우는 이런식으로 잡았고, 접근할 때 A[nx][ny][nz] 형태로 접근하게 된다. 이 문제를 풀 때 주의할 점은, 2667번

문제와 같이 모든 좌표를 돌면서 그 때 그 때 큐에 넣어주면 최단시간을 보장할 수 없다. 왜냐하면 저 문제는 단순히 BFS로 탐색한 영역의 수를 구하는거지만 이 문제는 배열 내에서 숫자가 퍼지는 시간을 구해야 하기때문에 미리 퍼질 수 있는 좌표를 큐에 넣어놓고 그 큐 안에서만 BFS를 돌려야한다. 이렇게 풀지 않을 경우 반례는 다음과 같다.

10 1 1
1 0 0 0 0 0 0 0 0 1