dx, dy 테크닉 기법

dx, dy 테크닉은 격자 문제나 방향 시뮬레이션 문제를 풀 때 유용하게 사용되는 기법. 방향 전환, 인덱스 고려 등을 추가로 신경 써야 하는 경우도 있다.

기본 개념

  • 방향이 dx, dy 배열의 인덱스가 됨.
  • 문제를 보면 먼저 격자나 그래프를 간단히 그림으로 그려보고, 각 방향에 맞는 x, y 증감값을 설정.

예시

// 방향 순서: 서(w), 북(n), 남(s), 동(e)
dx[4] = {-1, 0, 0, 1};
dy[4] = {0, 1, -1, 0};

문제 풀이 순서

  1. dx, dy 배열을 먼저 작성.
  2. 문제의 요구사항에 맞게 방향과 이동을 구현.

방향 전환

  • 방향 전환은 curr_dir 변수로 관리.

반시계 방향 90도 회전

curr_dir = (curr_dir - 1 + 4) % 4;

시계 방향 90도 회전

curr_dir = (curr_dir + 1) % 4;

격자 문제에서의 주의점

  1. dx, dy 테크닉 활용하기.
  2. 인덱스가 0부터 시작인지, 1부터 시작인지 확인.
  3. 격자에서의 (x, y)는 2차원 배열의 (i, j)와 동일.
    • 각각을 행(row, r), **열(column, c)**로 생각.
    • 그림을 그려 dx, dy를 구성.

예시: 동서남북

// 동, 남, 서, 북
dx = {0, 1, 0, -1};
dy = {1, 0, -1, 0};

  1. 인덱스 범위 오류 주의!

    • nx, ny가 격자 안에 있는지 확인하는 bool 함수 설계.

    • 조건문에서 함수 순서를 신경 쓰기:

      if (InRange && condition) { // 올바른 순서
    ...
}

if (condition && InRange) { // 예상치 못한 결과 발생 가능
    ...
}

범위 확인 함수 예시

bool InRange(int nx, int ny, int n, int m) {
    return nx >= 0 && ny >= 0 && nx < n && ny < m;
}