알고리즘 특강 1일차 : dx, dy 테크닉

dx,dy 테크닉은 좌표를 상하좌우로 움직이는 알고리즘을 풀 때 주로 사용하는 방법이다.

사실 이 방식은 문제를 풀고 다른 사람 코드랑 비교하는 과정에서 많이 보았는데, 그냥 편해서 사용하는줄만 알았던 코드가 하나의 알고리즘 개념이었다니 신기했고, 앞으로는 이 방법을 적극적으로 이용해야겠다는 생각이 들었다!

 

0이 입력되면 동쪽으로, 1이 입력되면 남쪽으로, 2가 입력되면 서쪽으로 , 3이 주어지면 북쪽으로 가는 코드를 짜려고 한다. 

 

int nowNum = 0;

int x = 1;
int y = 1;

if(nowNum == 0){
  x++;
  }
  
else if(nowNum = 1){
  y--;
  }
  
else if(nowNum = 2){
  x--;
  }
  
else if(nowNum =3){
  y++;
  }

이러한 방식으로 코드를 짜면 직관적일 수는 있지만, 오류가 발생할 확률이 높고, 현업에서 프로젝트를 할 때 비효율적일 수 있다.

 

따라서 이때 쓰는 방법이 dx,dy테크닉이다.

 

dx dy 배열에는 위와 같이 1과 -1을 엇갈아 넣어준다.

이를 활용하면,

int nowNum = 2;

int x = 1;
int y = 2;

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

x += dx[nowNum];
y += dy[nowNum];

이렇게 간단하게 코드를 짤 수 있다.

 

회전문제에 적용하는 방법

 

어떠한 명령이 주어지면 90도로 회전하는 문제 역시 이 테크닉을 이용하여 풀 수 있다.

 

현 위치를 나타내는 변수가 있고, 이 변수가 0이면 동쪽, 1이면 남쪽, 2이면 서쪽, 3이면 북쪽을 나타낸다고 했을 때,시계방향으로 회전하는 문제에서 90도로 돌으라는 명령어를 받으면 현재 위치에 1을 더하면 된다.

이때 3에서 1을 더하면 4가 아니라 0이 되어야 하므로  (현재 변수 +1 ) % 4 를 하면 된다.

 

만약 반시계방향으로 한다면? -1을 할 수도 있지만 처리하기가 더욱 어렵다. 이럴 때에는 반시계방향으로 한번 이동한 값이 시계방향으로 3만큼 이동한 값이랑 같다는 것을 이용하면 된다.

 

인접한 격자 탐색하기

 

위와 같이 dx dy 배열을 만들고, 이를 차례로 더하거나 빼서 인접한 격자를 탐색하면 된다. 이 때 해당 배열을 더하거나 뺐을 때 이 격자가 존재하는지를 알아보는 과정이 꼭 필요하다.

 

int nowNum = 2;

int x = 1;
int y = 2;

int[][] a = { 
            {0, 0, 0, 1, 0},
            {0, 1, 1, 1, 0},
            {0, 0, 0, 0, 1},
            {1, 0, 1, 1, 1},
            {1, 0, 1, 1, 0}
        };

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

x += dx[nowNum]; 
y += dy[nowNum];

System.out.println(a[x][y] == 0); // 만약 x가 -1이면 해당 격자는 존재하지 않으므로 에러가 발생한다.

그리고 일정한 범위 안에서 0과 1이 있을 때 1의 갯수를 세고 싶으면 이를 다 더하는 것도 하나의 방법이다.

 

돌면서 숫자 적기

 

1	2	3	4	5
14	15	16	17	6
13	20	19	18	7
12	11	10	9	8

이와 같이 돌면서 숫자를 채워주는 기능을 구현 할 때에도 dx dy 배열을 사용한다. 

위에서 회전문제에서 사용한 방법과 동일한데, 방향을 나타내는 변수를 하나 생성하고, (변수 + 1)%4 을 사용하여 방향을 정해준다. 탐색 중 길이 막혔을 때 회전하는 것을 구현을 잘 하면 된다.

 

import java.io.*;
import java.util.*;
import java.math.*;


public class Main {
    public static void main(String[] args) throws IOException{

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        int[][] arr = new int[n][m];

        int num = 1;

        int x = 0;
        int y = 0;
        int d = 0;
        arr[x][y] = 1;

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


        while(num != n*m){
            if(x + dx[d] < 0 || x + dx[d] >= n || y + dy[d] < 0 || y + dy[d] >= m ||
               arr[x + dx[d]][y + dy[d]] != 0){

                d = (d +1) % 4;
               }
               num++;  

              x += dx[d]; 
              y += dy[d];

               arr[x][y] = num;
               

        }

        for(int i = 0;i<n;i++){
            for(int j = 0;j<m;j++){
                System.out.printf("%d ",arr[i][j]);
            }
            System.out.println();
        }

        


    }
}

위와 같이 현재 방향에서 직진했을 때 array를 벗어난다거나, 값이 0이 아닐 때 (이미 채워져 있을 때)에는 회전하게 한다.