dx dy 테크닉

완전탐색의 기본

격자에서의 완전탐색을 해야한다면, 바로 이 테크닉이다.
dfs, bfs, 완전탐색 시뮬레이션 등등 아마 제일 많이 사용되는 테크닉 아닐까 생각된다.

구현방법은 간단하다.

#include <iostream>

int main() {
    int dxs[4] = {-1,0,1,0};
    int dys[4] = {0,1,0,-1};
    int nx;
    int ny;
    int x = 0;
    int y = 0;

    for i in range(4):
        nx = x + dxs[i];
        ny = y + dys[i];
        
}

이런식으로 4방향으로 이동할 수 있는 좌표를 만들고, 그 방향으로 이동하도록 for 문을 돌리면 된다.

방향 전환

만약 특정 조건에서 방향을 전환해야하는 문제가 나온다면 dxs dys 순서를 잘 지정해야한다.

예를 들어 위 오른쪽 아래 왼쪽 순서대로 진행된다고 하면, dxs, dys는

#include <iostream>

int main() {
    int dxs[4] = {0,1,0,-1};
    int dys[4] = {1,0,-1,0};
    int nx;
    int ny;
    int x = 0;
    int y = 0;

    for i in range(4):
        nx = x + dxs[i];
        ny = y + dys[i];
        
}

과 같은 순서를 가져야한다.
그리고 dir_num은
(dir + 1) % 4 ==> 시계방향
(dir + 3) % 4 ==> 반시계방향

이런식으로 설정해야한다.

이제 단순 시계방향 전환 외에도 다양한 전환이 나오게 될건데, 그때마다 적당한 설정과 dir 설정이 필요하다.
예를 들어 벽에 부딫히면 방향 반전은 (dir + 2) % 4로 처리한다.

이는 함수좌표에서의 예시이고 격자에서라면 위로 올라가려면 x 좌표가 -1이 되어야한다.

이게 끝이다. 하지만 엄청 자주 사용되는 기본 로직이다.