[C#/Programmers] Lv2. 방문 길이

Lv2 문제이다.

 

Winter Coding 에서 테스트로 나왔던 기출문제이다.

 

 

문제가 좀 길다.

---

생각 해 보기

문제는 길긴 하지만 생각보다는 별거 없다.

 

우선, 좌표계가 한정되어 있고, 이미 갔던 길을 중복해서 체크하지 않아야 하기 때문에 별도로 체크를 해 주는 자료구조를 하나 만들어야 함을 생각해야 한다.

 

나는 이차원 배열 두 개를 만들어 주었다.

 

왜 두개를 만들었냐 하면 좌표계의 한 점에서 갈 수 있는 것이 상, 하, 좌, 우의 네 가지 길이 있다. 상/하를 한 세트로 해서 갔던 길을 저장하는 배열 하나, 좌/우를 한 세트로 해서 갔던 길을 저장하는 배열을 하나 만들어 주었다.

up, right 배열

즉, 위 그림과 같이 좌표에서 오른쪽길을 통과했는지 여부를 담는 Right 배열, 위쪽 길을 통과했는지 여부를 담는 Up배열 두 개를 만들어 주면 된다.

 

방향은 오른쪽, 위쪽만 만들어 두어 일관성을 가지게 하였다.

 

---

코드(C#)

 

using System;

public class Solution {
    public int solution(string dirs) {
        int answer = 0;
        
        int x = 0;
        int y = 0;
        
        bool[,] upArr = new bool[11,10];
        bool[,] rightArr = new bool[10,11];
        
        foreach(char i in dirs){
            switch(i){
                case 'U':
                    if(y >= 5)
                        break;
                    if(upArr[x+5,y+5]== true){
                        y++;
                        break;
                    }
                    else{
                        upArr[x+5,y+5] = true;
                        y++;
                        answer++;
                    }
                    break;
                case 'D':
                    if(y <= -5)
                        break;
                    y--;
                    if(upArr[x+5,y+5] == true)
                        break;
                    else{
                        upArr[x+5,y+5] = true;
                        answer++;
                    }
                    break;
                case 'R':
                    if(x >= 5)
                        break;
                    if(rightArr[x+5,y+5] == true){
                        x++;
                        break;
                    }  
                    else{
                        rightArr[x+5,y+5] = true;
                        x++;
                        answer++;
                    }
                    break;
                case 'L':
                    if(x <= -5)
                        break;
                    x--;
                    if(rightArr[x+5,y+5] == true){
                        break;
                    }
                    else{
                        rightArr[x+5,y+5] = true;
                        answer++;
                    }
                    
                    break;
                    
            }
            
            
        }
        
        return answer;

    }
    
}

여기서 좌표를 나타내는 x,y는 좌표숫자를 그대로 사용하였지만 배열index에서는 +5를 더해 주어 사용하였다.

 

그리고 위 그림과 같이 right 배열은 가로 10, 세로 11의 크기로 만들었으며, up은 그 반대인 11x10의 크기로 제작하였다.

 

그리고 한 번 지나간 길은 배열의 원소를 true로 바꾸어 주었으며, 이미 true일 경우에는 다음 바퀴를 돌게끔 하였다.

 

위 배열들은 해당 좌표에서 오른쪽, 위쪽 방향으로의 길을 체크하는 것이다. 즉, ‘L’(과 ‘D’)의 경우에는 한 칸을 먼저 좌측(아래쪽)으로 옮긴 다음에 옮긴 지점에서 오른쪽(위쪽)으로 이동하는 길이 true가 되어 있는가 확인 해 준다.

 

---

실수했던 부분

 

‘U’(와 ‘R’) 부분에서 이미 길이 true가 되어 있을 때 길 체크만 하고 y(x)좌표를 더하지 않고 바로 break;를 건 부분이었다.

 

“LRLR” 이렇게 한 길을 반복하는 경우에 ‘L’로 왼쪽으로 간 다음에 ‘R’이 들어왔을 때, 길 체크만 하고 다시 오른쪽으로 이동하지 못하여서 ‘L’이 다시 들어오게 되면 왼쪽 칸으로 한 번 더 이동하게 된 것 같은 효과가 나게 되어 answer이 예기치 못하게 늘어나게 되었다..

 

따라서 ‘R’(, ‘U’)의 경우에서 이미 지나 간 길일 때 x(y)좌표를 break; 전에 늘려주는 작업을 해 주니 의도했던 대로 작동하였다.