dx, dy 테크닉 공부

dx, dy 테크닉

dx, dy 테크닉 파트는 내가 코드트리를 알게 된 계기이다. 프로그래머스에서 문제 풀다가 dx, dy를 이용해서 문제를 푸는데 이해가 잘 가지 않아서 검색하다가 한 블로그에서 dx, dy 테크닉을 언급해서 기대하고 있던 파트이다.

int dirNum = 2;  
int x = 1, y = 5; 
int[] dx = new int[]{1,  0, -1, 0};
int[] dy = new int[]{0, -1,  0, 1};
int nx, ny;

if(dirNum == 0) {
    nx = x + dx[0]; ny = y + dy[0];
}
else if(dirNum == 1) {
    nx = x + dx[1]; ny = y + dy[1];
}
else if(dirNum == 2) {
    nx = x + dx[2]; ny = y + dy[2];
}
else {
    nx = x + dx[3]; ny = y + dy[3];
}

이 파트부터 봤으면 잘 이해가 안 갔을 수도 있는데, 이전에 구간 칠하기 파트에서 다뤘던 한 인덱스에서 서로 다른 배열을 한번에 사용했던 경험 덕분에 더 잘 이해 되었다.

핵심 아이디어는 if문으로 비슷한 코드를 계속 입력하는 대신 서로 다른 배열을 한 인덱스에 묶어서 사용하는 것이다.

나중에 DFS, BFS에서도 많이 사용되었던 걸로 기억한다.

처음에 봤을 때 궁금했던 것 중에 하나가

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

왜 이렇게 0, -1, 0, 1처럼 0과 1을 번갈아가면서 사용하는지 궁금했다.

그 이유는 이렇게 사용하면 시계, 반시계 방향으로 전환하기가 쉬워지기 때문이다.

dx, dy와 배열

조건에 따라 방향이 변하는 경우

개인적으로 이 부분이 제일 헷갈렸다.(프로그래머스에서 비슷한 문제 풀 때도 이 부분 때문에 잘 이해가 안 갔다.)

dx, dy는 좌표로 사용될 때와는 다르게 배열로 사용될 때는 주의해야 한다.

행은 dy에, 열은 dx에 대응되는데, arr[dy][dx] 이런 느낌이다.

헷갈리기 딱 좋기 때문에 주의해야 한다.

이제 풀이를 하나씩 뜯어보자.

public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();
        t = sc.nextInt();

        mapper['R'] = 0;
        mapper['D'] = 1;
        mapper['U'] = 2;
        mapper['L'] = 3;

        x = sc.nextInt();
        y = sc.nextInt();
        char cDir = sc.next().charAt(0);
        x--; y--; dir = mapper[cDir];

        simulate();

        System.out.println((x + 1) + " " + (y + 1));
    }

먼저 mapper 부분부터 살펴보면

mapper['R'] = 0;
mapper['D'] = 1;
mapper['U'] = 2;
mapper['L'] = 3;

이 부분은 if로 각 케이스를 나눠주었던 것을 배열로 단순화 해준 것 같다.

여기서 주의할 점은 char 타입의 아스키코드라서 숫자로 변환되기 때문에 아래와 같이 배열을 선언해주어야 한다.

public static final int ASCII_NUM = 128;
public static int[] mapper = new int[ASCII_NUM];

또 이해가 안 갔던 부분은

x--; y--;
//...
System.out.println((x + 1) + " " + (y + 1));

이렇게 빼주는 이유가 궁금했는데, 좌표에서는 0, 0이 있지만 배열에서는 1행, 1열부터 시작하기 때문에 이 차이를 맞춰주기 위해서 1을 빼주었다가 나중에 다시 1을 더해주는 것이었다.

dx, dy 빙빙 돌기

빙빙 돌며 숫자 사각형 채우기

빙빙 돌면서 숫자를 채워나가는 문제이다.

어떻게든 풀긴 했는데, 뭔가 의식 흐름대로 풀어서 한번 해설 풀이랑 비교를 해봤다.

처음 풀이

import java.util.*;
public class Main {
    public static final int MAX_N = 100;
    public static final int N = 4;
    public static int n, m, nx, ny, dir;
    public static int[][] arr = new int[MAX_N][MAX_N];
    public static int[] dx = new int[]{0, 1, 0, -1};
    public static int[] dy = new int[]{1, 0, -1, 0};
    public static boolean inRange(int x, int y){
        return 0 <= x && x < n && 0 <= y && y < m;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        int count = 1;
        for(int i=0; i<=n; i++){
            for(int j=0; j<=m; j++){
                if(inRange(nx, ny) && arr[nx][ny] == 0){
                    arr[nx][ny] = count++;
                } else{
                    nx -= dx[dir]; 
                    ny -= dy[dir];
                    dir = (dir + 1) % 4; 
                }
                nx += dx[dir]; 
                ny += dy[dir];
            }
        }
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                System.out.print(arr[i][j] + " ");
            }
            System.out.println();
        }
    }
}

처음 내 풀이는
1. 정상 범위이면 숫자 채우기
2. 아니면 뒤로 가서 방향 전환하기
3. 이동하기

for(int i=0; i<=n; i++){
    for(int j=0; j<=m; j++){
        if(inRange(nx, ny) && arr[nx][ny] == 0){
            arr[nx][ny] = count++;
        } else{
            nx -= dx[dir]; 
            ny -= dy[dir];
            dir = (dir + 1) % 4; 
        }
        nx += dx[dir]; 
        ny += dy[dir];
    }
}

근데 이 풀이보다 해설 풀이가 더 좋은 풀이인것 같다.

해설

public class Main {
    public static final int MAX_NUM = 100;
    public static final int DIR_NUM = 4;

    public static int n, m;
    public static int[][] arr = new int[MAX_NUM][MAX_NUM];

    public static int[] dx = new int[]{0, 1,  0, -1};
    public static int[] dy = new int[]{1, 0, -1,  0};

    public static int currX = 0, currY = 0;  // 시작은 (0, 0) 입니다.
    public static int dir = 0;               // 0: 오른쪽, 1: 아래쪽, 2: 왼쪽, 3: 위쪽

    public static boolean inRange(int x, int y) {
        return 0 <= x && x < n && 0 <= y && y < m;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        // 입력
        n = sc.nextInt();
        m = sc.nextInt();

        // 처음 시작 위치에 초기값을 적습니다.
        arr[currX][currY] = 1;

        // n*m개의 숫자를 적어야 합니다.
        for(int i = 2; i <= n * m; i++) { // 숫자 i를 어디에 적을지 결정합니다.
            // 현재 방향 dir를 기준으로 그 다음 위치 값을 계산합니다.
            int nextX = currX + dx[dir], nextY = currY + dy[dir];

            // 더 이상 나아갈 수 없다면
            // 시계방향으로 90'를 회전합니다.
            if(!inRange(nextX, nextY) || arr[nextX][nextY] != 0)
                dir = (dir + 1) % 4;

            // 그 다음 위치로 이동한 다음 배열에 올바른 값을 채워넣습니다.
            currX = currX + dx[dir]; currY = currY + dy[dir];
            arr[currX][currY] = i;
        }

        // 출력:
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++)
                System.out.print(arr[i][j] + " ");
            System.out.println();
        }
    }
}

해설 풀이를 요약하면
1. 방향 계산하기
2. 올바른 범위인지 검증, 아니면 방향 전환
3. 이동하기

내 풀이는 의식 흐름대로 풀었다면 해설 풀이는 방향 계산 -> 검증 -> 이동으로 직관적이라서 더 좋은 풀이인 것 같다.

뭔가 일반화해두기 좋은 풀이랄까