[코딩테스트] 구현(Implement)과 dx, dy 테크닉

패스트캠퍼스x야놀자 백엔드 부트캠프 중 

[자료구조 및 알고리즘] 김태원 강사님 강좌를 듣고 정리한 내용입니다.

구현 문제란?

작은 의미로는 문제가 제시한 규칙에 따라 개체를 이동시키는 알고리즘을 의미하며, 

큰 의미로는 문제가 요구하는 대로 시행되도록 코드를 구현하는 알고리즘이다.

 

개체이동방법

개체이동방법은 두가지가 있다.

• 4방향 탐색 
• 8방향 탐색

4방향 탐색 방법

위와 같이 좌표를 가진 x, y 그래프를 코딩테스트에서는 2차원 배열로 표기가 된다.

구현 문제를 풀다보면 해당 좌표에서의 이동이 기본 베이스로 필요할 때가 있다. 

 

우선 4방향 탐색을 알아보자.

 

[r, c]의 상하좌우 이동 시 값의 변화

[2, 1] - 기본값

[1, 1] - 상 
[3, 1] - 하
[2, 0] - 좌
[2, 2] - 우

[r, c]의 상하좌우 이동 시 x, y 값의 변화

[1, 1] - 상  =  [-1, 0]
[3, 1] - 하  =  [1,0]
[2, 0] - 좌  =  [0,-1]
[2, 2] - 우  =  [0,1]

특정 좌표에서 4방향으로 이동하면 xy값이 어떻게 변하는 지 알 수 있다. 우린 이것을 활용하여 좌표이동을 진행하면 된다.  강의에서 쉽게 외우기 위해선 방향을 고정적으로 정하는 것이 중요하다고 하였다. 그래서 12시부터 시계방향으로 작성하여 진행하였다. 

 

4방향 표기

// dx, dy 배열
// 12시, 3시, 6시, 9시 순이다.

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

• 코딩 테스트에서는 dx, dy를 int의 1차원 배열로 표기한다. 
• 12시, 3시, 6시, 9시 순으로 시계방향 순으로 지정한다. 

 

8방향 탐색 방법

// dx, dy 배열

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

8방향은 4방향에서 대각선 방향이 추가된 것이다. 마찬가지로 시계방향으로 진행한다. 

 

dx, dy 테크닉 

위에 지정한 방향배열로 dx, dy 테크닉을 알아보자. 

 

단순 방향 이동방법 

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

// 출발 지점 설정 
int x = 0, y = 0;
// 이동 방향을 나타낸다.
int dir = 0;

// 이동 방향에 따른 이동 
int nx = x + dx[dir];
int ny = y + dy[dir];

 

방향 회전 문제에서의 이동방법

문제를 풀다보면 방향을 시계방향 또는 반시계방향으로 변경필요한 경우가 생긴다. 그때 사용하면 유용한 방법이다. 

// 12, 3, 6, 9시 순으로 진행된다.
int[] dx = {-1, 0, 1, 0};
int[] dy = {0, 1, 0, -1};

// 출발 지점 설정 
int x = 0, y = 0;
// 초기 이동 방향을 나타낸다.
// 1은 3시방향이다.
int dir = 1;

// 시계 방향으로 90도 회전
// 1 -> 2
// 2 -> 3
// 3 -> 0
// 0 -> 1

dir = (dir+1) % 4;

int nx = x + dx[dir];
int ny = y + dy[dir];

// 반시계 방향으로 90도 회전
// 1 -> 0
// 0 -> 3
// 3 -> 2
// 2 -> 1

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

int nx = x + dx[dir];
int ny = y + dy[dir];

dx, dy 배열을 시계방향 순으로 입력했기 때문에 시계 방향으로 90도 회전하는 것은 배열의 인덱스 값을 1씩 증가시키는 것 이므로 dir을 1 증가시키는 것과 같다.

 

1를 무한으로 증가하면 배열의 범의를 초과함으로 [% 4] 과정이 들어가는 것이다. 

 

반시계 방향으로 회전하는 경우에는 시계방향과 반대로 dir을 1씩 빼주면 되는데 이 경우에도 마찬가지로 dir이 0이면 -1이 되므로 범위를 초과하게 된다. 

 

이 경우에도 위에 방법과 유사하게 이를 해결하는데 dir = (dir -1 + 4) % 4를 사용한다.

 

격자 속 dx, dy 범위초과 조건

코딩테스트에서 주어지는 2차원 배열은 모두 범위가 존재한다. 

그렇기 때문에 방향 이동 시 범위를 초과하는 케이스를 방지하는 조건이 필요하다. 

 

다음 예제로 확인해 보자.

명령어에 따른 이동 규칙이 있는 로봇이 있다고 가정한다.

 

1. 'U' 명령은 로봇이 위쪽으로 한 칸 이동
2. 'R' 명령은 로봇이 오른쪽으로 한 칸 이동
3. 'L' 명령은 로봇이 왼쪽으로 한 칸 이동
4. 'D' 명령은 로봇이 아래쪽으로 한 칸 이동
5. 만약 로봇이 명령을 수행할 경우 격자판 밖으로 나가는 경우라면 로봇은 해당 명령을 수행
하지 않고 무시

 

최종적으로 로봇의 위치를 반환한다.

 

매개변수

• n은 격자판의 크기 (ex. n = 5)
• moves는 청소로봇에 명령을 내린 문자열이다. (ex. moves = "RRRDDDUUUUUUL")

public int[] solution(int n, String moves){
    int[] dx = {-1,0,1,0};
    int[] dy = {0,1,0,-1};
    int[] dir = {'U','R','D','L'};

    int x = 0, y = 0;

    for(char command : moves.toCharArray()){
        for(int k = 0; k < 4; k++){
            if(command == dir[k]){
                int cx = x + dx[k];
                int cy = y + dy[k];

                // 범위가 벗어나는 조건 추가
                if(cx < 0 || cx >= n || cy < 0 || cy >= n){
                   break;
                }
                
                x = cx;
                y = cy;
            }
        }
    }

    return new int[]{r,c};
}

위 문제에 주어진 것처럼 주어진 격자판의 크기가 n이다.  이 말은 결국 x, y의 크기가 [0 ~ n-1] 사이어야 한다는 의미이다.

문제를 풀때 해당 범위를 초과한 값들은 모두 제외시켜주는 조건을 만들어야 한다.

 

 

풀어봐야 할 프로그래머스 문제

프로그래머스 Lv.0 - 안전지대

프로그래머스 Lv.0 - 정수를 나선형으로 배치

프로그래머스 Lv.1 - 공원 산책

프로그래머스 Lv.1 - 키패드 누르기