[C++#2-2] 이동 알고리즘

구현의 두번째, 이동 알고리즘이다.

내가 생각하기엔 이동 알고리즘부터 본격적인 구현의 내용이라 생각한다.

이동 알고리즘의 최종적인 목표는 2차원 or 3차원 상의 좌표에서, 1명 or n명의 이동을 코드로 나타내는 것이다.

1. 이동 알고리즘

1-1. 1차원 이동

아래와 같은 맵에서 사람이 오른쪽으로 이동하는 모습을 코드로 구현하면 어떻게 해야할까?

일단 맵을 표현하는 방법은 여러가지가 있지만, 이 게시물에서는 1차원, 2차원 맵 모두 배열로 표현했다.

 
int arr[6] = { 1, 0, 0, 0, 0, 0 };
 

사람을 오른쪽으로 이동시키기 위해서는 위 코드처럼,

초기 위치인 인덱스 0번을 0으로 만들고, 인덱스 1번을 1로 만들어서 이동시키는 것을 구현할 수 있다.

위 코드를 넣으면 아래와 같이 배열에서 이동되는 모습을 얻을 수 있을 것이다.

하지만 이는 우리가 그림을 통해 직관적으로 사람의 위치를 알 때의 이야기이고, 먼저 배열에서 사람이 어디 있는지 파악해야 한다.

사람을 찾아서 이동하는 것까지 코드를 구현하면 다음과 같은 코드를 작성할 수 있다.

 
int location;
 
int arr[6] = { 1, 0, 0, 0, 0, 0 };
for(int i = 0; i < 6; i++){
   if(arr[i] == 1) location = i;   
}
 
arr[location] = 0;
location++;
arr[location] = 1;
 

사람이 1명일 때, 배열에서 1의 값은 무조건 하나이므로,

배열의 인덱스가 1일 때 위치를 저장하고,

해당 위치를 0으로 만든 후,

그 다음(+1)의 위치를 1로 만든다.

 

반대로 위 그림처럼 사람이 왼쪽으로 이동하는 코드를 구현하고 싶다면, 

 
int location;
 
int arr[6] = { 0, 0, 0, 0, 0, 1 };
for(int i = 0; i < 6; i++){
   if(arr[i] == 1) location = i;   
}
 
arr[location] = 0;
location--;
arr[location] = 1;
 

위 코드처럼 우로 이동하는 코드와 마찬가지의 과정으로 방향만 바꿔준다면 쉽게 아래와 같은 결과를 얻을 수 있다.

1-2. 2차원 이동

코딩테스트의 문제들을 보면(내경우에는) 주로 2차원 Map구현에 대한 문제가 많이 나왔던 것 같다.

2차원 맵 또한 1차원 이동의 맵 구현과 크게 다르진 않다.

다만 1차원 배열 대신 2차원 배열이 사용되고, 상하 이동에서 행이동을 해줘야 된다는 점이 다르다.

1차원 이동에서 했던 것 처럼 

맵 생성 -> 조회 -> 이동 순으로 똑같이 코드를 짜면 아래와 같은 코드가 된다.

 
int y, x;
 
int arr[3][6] = { { 0, 0, 0, 0, 1, 0 },
               { 0, 0, 0, 0, 0, 0 },
               { 0, 0, 0, 0, 0, 0 } };
for(int i = 0; i < 3; i++){
    for(int j = 0; j < 6; j++){
        if(arr[i][j] == 1) {
            y = i;
            x = j;
        }
    }
}
 
arr[y][x] = 0;
y++;
arr[y][x] = 1;
 

1차원 이동과 다른 점은 위치 기억을 위한 좌표가 location 하나에서 y, x 두개로 바뀌고, 맵이 2차원 배열로 바뀌었다.

이 코드를 이용하면 아래와 같은 결과를 얻을 수 있다.

마찬가지로 아래 그림처럼 위로 이동해야 하는 상황에서도

아래 코드처럼 y(세로축)의 방향만 변경해주면

 
int y, x;
 
int arr[3][6] = { { 0, 0, 0, 0, 1, 0 },
               { 0, 0, 0, 0, 0, 0 },
               { 0, 0, 0, 0, 0, 0 } };
for(int i = 0; i < 3; i++){
    for(int j = 0; j < 6; j++){
        if(arr[i][j] == 1) {
            y = i;
            x = j;
        }
    }
}
 
arr[y][x] = 0;
y--;
arr[y][x] = 1;
 

아래 사진 처럼 위로 이동하는 결과를 나타낼 수 있다.

1-2-1. dy, dx

그런데 위처럼 x방향, y방향을 직접 변경해주려면 아래처럼 상, 하, 좌, 우 4가지 경우의 수에 따라서 4가지의 조건문을 설정해 주어야 한다.

if(dir == "EAST"){
    //동쪽 이동
}
if(dir == "WEST"){
    //서쪽 이동
}
if(dir == "SOUTH"){
    //남쪽 이동
}
if(dir == "NORTH"){
    //북쪽 이동
}

동서남북에 따라 X값과 Y값의 변화를 나타낸 것이다.

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

이를 배열에 저장하면 다음과 같이 된다.

( 순서는 0, 1, 2, 3 순으로 동, 서, 남, 북 )

별거 아니라고 생각할수 있지만, 방향 배열을 설정해서 이동을 구현하면 코드를 작성할때 시간을 많이 절약할 수 있다.

dy, dx를 적용해서 2차원 맵에서 위로 이동하는 것을 구현하면 아래와 같다.

 
int y, x;
int dy[4] = { 0, 0, 1,-1 };
int dx[4] = {-1, 1, 0, 0 };
int dir;// 방향 동 : 0, 서 : 1, 남 : 2, 북 : 3
 
int arr[3][6] = { { 0, 0, 0, 0, 0, 0 },
            { 0, 0, 0, 0, 0, 0 },
            { 0, 0, 0, 0, 1, 0 } };
for(int i = 0; i < 3; i++){
   for(int j = 0; j < 6; j++){
      if(arr[i][j] == 1) {
         y = i;
         x = j;
      }
   }
}
 
dir = 3; // 방향 : 북
 
arr[y][x] = 0;
y += dy[dir];
x += dx[dir];
arr[y][x] = 1;
 

 

1-3. 큰 이동

큰 이동이라 함은 여러 칸을 한번에 이동하는 것을 말한다.

사실 큰 이동은 진짜 쉽다.

위에서 했던 이동 알고리즘을 반복문안에 넣어주기만 하면 된다.

dy, dx를 적용한 코드에서 반복문만 추가해서 다음과 같은 코드를 작성했다.

 
int y, x;
int dy[4] = { 0, 0, 1,-1 };
int dx[4] = {-1, 1, 0, 0 };
int dir;// 방향 동 : 0, 서 : 1, 남 : 2, 북 : 3
int distance; //이동 거리
 
int arr[3][6] = { { 0, 0, 0, 0, 0, 0 },
            { 1, 0, 0, 0, 0, 0 },
            { 0, 0, 0, 0, 0, 0 } };
for(int i = 0; i < 3; i++){
   for(int j = 0; j < 6; j++){
      if(arr[i][j] == 1) {
         y = i;
         x = j;
      }
   }
}
 
dir = 1; // 방향 : 서
distance = 3; // 거리 : 3
for(int i = 0; i < distance; i++)
{    
    arr[y][x] = 0;
    y += dy[dir];
    x += dx[dir];
    arr[y][x] = 1;
}

다음 코드를 통해 아래와 같은 결과를 얻을 수 있다.

상하 이동도 위의 코드에서 방향, 거리만 바꾸면 구현할 수 있으므로 생략하도록 하겠다.

큰 이동까지 했으면 이동에 대해 거의 끝났다고 볼 수 있다.

그런데 우리는 예외상황에 대해 생각해야 한다.

다음 내용이 바로 그 내용이다.

1-4. 경계, 장애물 처리

경계, 장애물은 처리하는 과정이 같아서 하나의 소제목으로 묶었다.

먼저 경계에 대해 설명하도록 하겠다.

1-4-1. 경계 처리

우리는 기존에 맵을 그릴 때 맵의 크기를 3x6으로 지정했다.

이동 알고리즘을 구현하면서 지정된 맵을 사람이 벗어나면 안된다.

맵의 크기를 넉넉히 잡았다면 맵 밖으로 벗어나는 상황이 되겠고, 

맵의 크기가 작거나, Y X 좌표가 0보다 작은 -1 값이 된다면 아예 빌드가 안되는 오류가 발생할 것이다.

이를 예방하기 위해 우리는 이동 알고리즘을 구현할 때 반드시 경계 처리를 해줘야 한다.

경계처리를 하는 방법은 두 가지 방법이 있다.

1-4-1-1. 맵에서 경계처리를 하는 방법

우리는 기존에 맵을 다음과 같이 나타냈다.

 
int arr[3][6] = { { 0, 0, 0, 0, 1, 0 },
                  { 0, 0, 0, 0, 0, 0 },
                  { 0, 0, 0, 0, 0, 0 } };
 

이 방법은 위의 방법보다 이해하기 더 어려울 수도 있지만, 이해하면 사용하기 더 편하다.

나는 주로 코딩테스트에서 이동알고리즘을 구현할 때 이 방법을 사용한다.

 
int y, x;
int ny, nx;// 이동을 위한 nextY, nextX
int dy[4] = { 0, 0, 1,-1 };
int dx[4] = {-1, 1, 0, 0 };
int dir;// 방향 동 : 0, 서 : 1, 남 : 2, 북 : 3
int distance; //이동 거리
int arr[3][6] = { { 0, 0, 0, 0, 1, 0 },
            { 0, 0, 0, 0, 0, 0 },
            { 0, 0, 0, 0, 0, 0 } };
for(int i = 0; i < 3; i++){
   for(int j = 0; j < 6; j++){
      if(arr[i][j] == 1) {
         y = i;
         x = j;
      }
   }
}
 
dir = 1; // 방향 : 서
distance = 3; // 거리 : 3
for(int i = 0; i < distance; i++)
{
    // 다음 좌표 지정
    ny = y + dy[dir];
    nx = x + dx[dir];
 
    // 다음 좌표가 맵을 벗어났을 때 반복문을 나감
    if(ny < 0 && ny >= 3 && nx < 0 && nx >=6 ) break;
   
    // 아니라면 위치 이동
    arr[y][x] = 0;
    arr[ny][nx] = 1;
 
    //이동된 위치 저장
    y = ny;
    x = nx;
}

위의 코드는 큰 이동에서 사용한 코드에서 코드를 수정한 것이다.

나름 이해가 쉽도록 주석을 달아놨는데 설명을 잘 한건지 모르겠다......

먼저 경계 처리를 위해 다음Y, 다음X 위치를 지정하고, 

다음Y, 다음X가 맵의 크기(경계)를 벗어났는지 확인한다.

벗어났다면 해당 위치에서 반복문을 종료하고, 벗어나지 않았다면 이동한다.

이 코드를 사용하면 아래의 상황에서

아래의 결과를 얻을 수 있다.

1-4-2. 장애물 처리

장애물 처리 역시 경계 처리와 같은 원리이다.

만약 맵에 장애물이 있다면 이동을 하는 과정에서 장애물 위에 있거나 장애물을 통과하면 안된다.

장애물의 경우 예외처리를 안하더라도 빌드 과정에서 오류가 발생하진 않지만, 우리가 원하는 문제에 대한 결과값을 얻을 수 없을 것이다.

장애물 처리 방법 역시 경계 처리 방법과 거의 동일하다.

코딩테스트 문제마다 다르지만 장애물의 경우 보통 -1로 처리한다.

코드는 경계 처리 - 맵을 한칸씩 확인 코드에서 추가했다.

 
int y, x;
int ny, nx;// 이동을 위한 nextY, nextX
int dy[4] = { 0, 0, 1,-1 };
int dx[4] = {-1, 1, 0, 0 };
int dir;// 방향 동 : 0, 서 : 1, 남 : 2, 북 : 3
int distance; //이동 거리
int arr[3][6] = { { 0, 0, 0, 0, 0, 0 },
            { 0, 0, 1,-1, 0, 0 },
            { 0, 0, 0, 0, 0, 0 } };
for(int i = 0; i < 3; i++){
   for(int j = 0; j < 6; j++){
      if(arr[i][j] == 1) {
         y = i;
         x = j;
      }
   }
}
 
dir = 1; // 방향 : 서
distance = 3; // 거리 : 3
for(int i = 0; i < distance; i++)
{
    // 다음 좌표 지정
    ny = y + dy[dir];
    nx = x + dx[dir];
 
    // 다음 좌표가 맵을 벗어났을 때 반복문을 나감
    if(ny < 0 && ny >= 3 && nx < 0 && nx >=6 ) break;
    // 다음 좌표가 장애물을 만났을 때
   if(arr[ny][nx] == -1 ) break;
 
    // 아니라면 위치 이동
    arr[y][x] = 0;
    arr[ny][nx] = 1;
 
    //이동된 위치 저장
    y = ny;
    x = nx;
}

코드에서 바뀐 부분은 맵에 -1로 표현된 장애물이 있는 것이랑,

31번째 줄에 장애물 처리를 해준 부분이다.

코드의 내용은 위에서 설명한 경계처리와 똑같으므로 생략하겠다.

1-5. N명 이동

N명 이동 까지 구현할 수 있다면, 이동 알고리즘에 대해서는 어지간한건 다 구현할 수 있다고 생각한다.

처음에 여러 사람(또는 로봇, 멧돼지 등)이 이동하는 맵을 구현하는 코딩테스트 문제를 보고 어떻게 구현할 지 막막했는데, 위의 순서대로 공부하니 어렵지 않게 구현할 수 있었다.

사실 위의 과정까지 다 구현했다면 N명 이동은 지금까지의 이동 과정을 여러번 동작 시켜주면 된다.

코드는 위의 장애물 처리 코드에서 추가했다.

 
int y[3]; //y좌표, 여러 명에 대한 배열
int x[3]; //x좌표, 여러 명에 대한 배열
int ny, nx;// 이동을 위한 nextY, nextX
int dy[4] = { 0, 0, 1,-1 };
int dx[4] = {-1, 1, 0, 0 };
int dir[3];// 방향 동 : 0, 서 : 1, 남 : 2, 북 : 3, 여러 명에 대한 배열
int distance[3]; //이동 거리, 여러 명에 대한 배열
int arr[3][6] = { { 1, 0, 0, 0, 0, 0 },
            { 0, 0, 1, 0, 0, 0 },
            { 0, 0, 0, 1, 0, 0 } };
int cnt = 0; // 여러 사람에 대한 정보 저장을 위한 변수
for(int i = 0; i < 3; i++){
   for(int j = 0; j < 6; j++){
      if(arr[i][j] == 1) {
         y[cnt] = i;
         x[cnt] = j;
         cnt++; // 사람 한명 증가
      }
   }
}
 
for(int t = 0; t <= cnt; t++){ //cnt명에 대한 이동
 
    dir[t] = t; // 0번 사람 방향 : 동, 1번 사람 방향 : 서, 2번 사람 방향 : 남
    distance[t] = t+1; // 0번 사람 거리 : 1, 1번 사람 거리 : 2, 2번 사람 거리 : 3
    for(int i = 0; i < distance[t]; i++)
    {
        // 다음 좌표 지정
        ny = y[t] + dy[dir[t]];
        nx = x[t] + dx[dir[t]];
    
        // 다음 좌표가 맵을 벗어났을 때 반복문을 나감
        if(ny < 0 && ny >= 3 && nx < 0 && nx >=6 ) break;
        // 다음 좌표가 장애물을 만났을 때
       if(arr[ny][nx] == -1 ) break;
    
        // 아니라면 위치 이동
       arr[y[t]][x[t]] = 0;
        arr[ny][nx] = 1;
    
        //이동된 위치 저장
       y[t] = ny;
       x[t] = nx;
    }
}

코드가 많이 복잡해진 것 같지만, 내용은 그렇게 어렵지 않다.

일단 기존에 한 사람의 이동을 위한 변수인 y(y좌표), x(x좌표), dir(방향), distance(거리) 를 여러 명의 이동을 위해 배열로 만들었다.

그리고 사람의 수를 세기 위한 변수인 cnt 변수를 추가했다.

여기서 주의해야 할 점은 cnt는 0번부터 사람을 세므로, 사람이 3명이라면 cnt는 값이 2가 된다.

그리고 기존에 한 사람의 이동을 구현한 코드에서 바깥쪽에 반복문 하나를 더 사용해서 여러 사람의 이동을 구현했다.

이동을 구현하는 과정에서 y, x, dir, distance 변수는 모두 배열 형태로 사용한다.

위의 코드를 사용하면 아래와 같은 사진에서

아래와 같은 결과를 얻을 수 있다.

*0번 사람은 방향이 동, 2번 사람은 방향이 남 이므로 경계를 만나 움직이지 않는다.

 

여기까지 혼자 할 수 있다면, 이동에 대한 구현은 어지간한 것은 할 수 있을 것이다.

추가적으로 학습하면 좋은 내용으로는 3차원 이동이 있는데,

이 부분은 아직 완벽하게 학습되지 않아 일단은 올리지 않기로 했다.

코딩테스트 문제를 공부하면서 난이도가 쉬운 내용이라 생각했는데, 글로 정리하려니 생각보다 오래걸렸다.....