[코드트리 챌린지] 거울에 레이저 쏘기 2

[문제]

https://www.codetree.ai/cote/13/problems/shoot-a-laser-in-the-mirror-2?&utm_source=clipboard&utm_medium=text 

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

[문제 풀이]

처음에 보면 어떤식으로 구현을 해야하는지 감이 잘 오지 않는 문제일 수 있다.

그러니 차근차근 나눠서 천천히 진행을 해보도록 하자.

 

우선 해당 문제를 풀기 위해서 시작 하는 위치 파악하기를 진행을 해보자.

숫자에 따라서 방향과 위치가 정해지고 이에 따라 x값과 y 값의 추론이 가능하다.

 

n이 3이라 3 * 3 배열일때 k 값이 1,2,3 인 경우 북쪽으로 향하고 행이 0으로 고정이 된다. 그리고 열의 값은 각각 (k - 1) % n 이 된다.

똑같이 n이 3일때 k가 4,5,6인 경우에는 서쪽으로 향하고 열의 값은 n - 1 로 고정이 되고 행의 값은 각각 (k - 1) % n 이 된다.

이제 남쪽의 경우 7,8,9 숫자일때 처음 값은 k - 1 로 고정이고 뒤의 값은 모두 n - 1  - ((k - 1 ) % n) 의 값이 나온다.

동쪽의 경우에는 열의값이 0으로 고정 행의 값이 n - 1 (k - 1 % n)이 나온다.

이를 코드로 작성하면

//북 동 남 서
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};

int temp = (k - 1) % n;
int x,y;
x = 0, y = 0;

if(n >= k){
    dict = 0;
    y = temp;
}
else if(n * 2 >= k){
    dict = 3;
    y = n - 1;
    x = temp;
}
else if(n * 3 >= k){
    dict = 2;
    x = n - 1;
    y = n - 1 - temp;
}
else if(n * 4 >= k){
    dict = 1;
    x = n - 1 - temp;
    y = 0;
}

 

이와 같은 코드가 작성이 가능하다. x값과 y값을 나느 arr[x][y]로 작성하기 때문에 바뀌어 있지만 arr[y][x] 로 작성하는 경우에는 해당 변수를 바꿔주면 된다.

 

이제 총 몇번을 튕기면서 범위 바깥으로 나가는지 파악해 주기 위해서 범위 바깥으로 나갔는지 아닌지 확인해주는 inRange()함수를 작성해주자.

bool inRange(int x, int y){
    if(x >= 0 && x < n && y >= 0 && y < n){
        return true;
    }
    return false;
}

 

마지막으로 이제 시작위치와 방향을 알았으니 반복문을 돌리면서 거울이 \와 / 의 경우에 어느 방향으로 바뀌는지를 파악하면서 해당 방향에 맞게 x값과 y값을 변동시켜 주자.

 

while(true){
    //1. / 인지
    //2. \ 인지 
    if(arr[x][y] == '\\'){
        // \ 거울일때 dict가 0(북)과 1(동)일때 같은 결과
        // dict가 3(서)과 2(남)일때 같은 결과가 나온다.
        //dict를 바꿔주고 해당 방향으로 x와 y 값 더해주기.
        if(dict == 0 or dict == 1){
            (dict == 0) ? dict = 1 : dict = 0;
        }
        else if(dict == 2 or dict == 3){
            (dict == 2) ? dict = 3 : dict = 2;
        }
    }
    else if(arr[x][y] == '/'){
        // /로 들어오면 0(북)과 3(서)이 서로 친구.
        // 1(동)과 2(남)이 친구
        // / 일때 0은 서쪽으로 가야 한다.
        if(dict == 0 or dict == 3){
            (dict == 0) ? dict = 3 : dict = 0;
        }
        else if(dict == 1 or dict == 2){
            (dict == 1) ? dict = 2 : dict = 1;
        }
    }
    x += dx[dict];
    y += dy[dict];
    if(inRange(x,y) == false){
        break;
    }
}

 

여기서 while문이 돌아가는 수 만큼을 더해주면 답이 나온다.

[회고]

생각보다 상당히 까다로웠던 문제. 방향값을 바꾸는데 우선 고생을 했고 다른 문제들과 다르게 dx, dy값을 바꾸기 위한 조건이 경우마다 달라서 결국 조건문을 통해 하드코딩을 해야만 했다.

if문을 줄이기 위해서 삼항연산자를 쓴 것은 좋은 선택이었던듯. 이건 좀 코드가 깔끔해져서 좋았다.

[코드]

#include <iostream>
#include <queue>

using namespace std;

int n;
//북 동 남 서
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};

char arr[1001][1001];

bool inRange(int x, int y){
    if(x >= 0 && x < n && y >= 0 && y < n){
        return true;
    }
    return false;
}

int main() {
    cin>>n;

    for(int i = 0;i<n;i++){
        for(int j = 0;j<n;j++){
            cin>>arr[i][j];
        }
    }
    //k에서 레이저 발사.
    int k;
    cin>>k;

    int dict = 0;
    int temp = (k - 1) % n;
    int x,y;
    x = 0, y = 0;
    if(n >= k){
        dict = 0;
        y = temp;
    }
    else if(n * 2 >= k){
        dict = 3;
        y = n - 1;
        x = temp;
    }
    else if(n * 3 >= k){
        dict = 2;
        x = n - 1;
        y = n - 1 - temp;
    }
    else if(n * 4 >= k){
        dict = 1;
        x = n - 1 - temp;
        y = 0;
    }

    //x,y좌표는 이제 알았고 
    //해당 위치와 방향을 아니 시작해보자.
    int answer = 0;
    while(true){
        answer++;
        //1. / 인지
        //2. \ 인지 
        if(arr[x][y] == '\\'){
            // \ 거울일때 dict가 0(북)과 1(동)일때 같은 결과
            // dict가 3(서)과 2(남)일때 같은 결과가 나온다.
            //dict를 바꿔주고 해당 방향으로 x와 y 값 더해주기.
            if(dict == 0 or dict == 1){
                (dict == 0) ? dict = 1 : dict = 0;
            }
            else if(dict == 2 or dict == 3){
                (dict == 2) ? dict = 3 : dict = 2;
            }
        }
        else if(arr[x][y] == '/'){
            // /로 들어오면 0(북)과 3(서)이 서로 친구.
            // 1(동)과 2(남)이 친구
            // / 일때 0은 서쪽으로 가야 한다.
            if(dict == 0 or dict == 3){
                (dict == 0) ? dict = 3 : dict = 0;
            }
            else if(dict == 1 or dict == 2){
                (dict == 1) ? dict = 2 : dict = 1;
            }
        }
        x += dx[dict];
        y += dy[dict];
        if(inRange(x,y) == false){
            break;
        }
    }
    cout<<answer<<endl;
    return 0;
}