[프로그래머스][C++] 빛의 경로 사이클

 

https://programmers.co.kr/learn/courses/30/lessons/86052

코딩테스트 연습 - 빛의 경로 사이클

 

글쓴이의 답

개인적인 풀이 임으로

이것보다 더 좋은 알고리즘은 많음...

이렇게도 풀이하는구나.. 공유하기 위해 올림...

이건 정말.. 내가 봐도 좀 무식하게 풀이한 것 같음

풀이 시간이 엄청 오래걸렸지만 

최대한 답을 확인하지 않고 내 머리로 풀기위해 노력해본 문제임.

코드가 더러워도 이해부탁함..

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

#define MAX 500

// [MAX][MAX][0]
// 0 : 빈곳
// 1 : S
// 2 : L
// 3 : R
// 10 : 경로

// [MAX][MAX][1], [MAX][MAX][2]
// [MAX][MAX][0] 인 경우 사용
// 0 : 지나가지 않음
// 1 : 지나감


int map[MAX*3+1][MAX*3+1][3] = {0, };

// 상, 하, 좌, 우
int moveH[4] = {-1, 1, 0, 0};
int moveW[4] = {0, 0, -1, 1};

int hSize=0;
int wSize=0;

int makeMap(int wSize, int hSize, vector<string> &grid){    
    int gridW =0;
    int gridH =0;        
    for(int i=0; i < hSize; i++){
        for(int k=0; k < wSize; k++){
            if(0 == i % 2){
                if(1 == k % 2){
                    map[i][k][0] = 10;
                }
            }
            else{
                if(0 == k % 2){
                    map[i][k][0] = 10;
                }
                else{
                    char temp = grid[gridH][gridW];
                    if('S' == temp){
                        map[i][k][0] = 1;
                    }
                    else if('L' == temp){
                        map[i][k][0] = 2;
                    }
                    else if('R' == temp){
                        map[i][k][0] = 3;
                    }                    
                    gridW++;
                }
                
            }
        }      
        if(1 == i % 2){
            gridH++;
            gridW=0;
        }        
    }
    return 0;
}

int checkInsertDirection(int locationH, int locationW, int prevH, int prevW){
    int direction =0;
    
    int checkH = locationH - prevH; // 1 = 위에서 아래, -1 = 아래서 위로 ,0 = 가로 확인
    int checkW = locationW - prevW; // 1 = 왼쪽에서 오른쪽, -1 = 오른쪽에서 왼쪽 ,0 = 세로 확인
    
    
	if (1 < checkH) {
		checkH = -1;
	}
	if (-1 > checkH) {
		checkH = 1;
	}
	if (1 < checkW) {
		checkW = -1;
	}
	if (-1 > checkW) {
		checkW = 1;
	}
    
    // 위에서 아래로 들어옴,
    if(1 == checkH){
        direction =1;
    }
    // 오른쪽에서 왼쪽으로 들어옴,
    else if(-1 == checkW){
        direction =2;
    }
    // 아래에서 위로 들어옴
    else if(-1 == checkH){
        direction =3;
    }
    // 왼쪽에서 오른쪽으로 들어옴
    else if(1 == checkW){
        direction =4;
    }
    
    return direction;
}



int cycle(int direction, int locationH, int locationW, int prevH, int prevW){
    int count = 0;
    
    while(map[locationH][locationW][direction] != 1){
        
        // 이동 경로인 경우
        if(10 == map[locationH][locationW][0]){
            map[locationH][locationW][direction] = 1;
            count++;
            int check = checkInsertDirection(locationH, locationW, prevH, prevW);
			int nextH = 0;
			int nextW = 0;
			if (1 == check) {
				nextH = locationH + 1;
				nextW = locationW;
				direction = 2;
			}
			else if (2 == check) {
				nextH = locationH;
				nextW = locationW - 1;
				direction = 1;
			}
			else if (3 == check) {
				nextH = locationH - 1;
				nextW = locationW;
				direction = 1;
			}
			else if (4 == check) {
				nextH = locationH;
				nextW = locationW + 1;
				direction = 2;
			}
			if (nextH < 0) {
				nextH = hSize - 1;
				count--;
			}
			else if (nextH == hSize) {
				nextH = 0;
				count--;
			}
			if (nextW < 0) {
				nextW = wSize - 1;
				count--;
			}
			else if (nextW == wSize) {
				nextW = 0;
				count--;
			}
			prevH = locationH;
			prevW = locationW;
			locationH = nextH;
			locationW = nextW;
        }
        // S인 경우
        else if(1 == map[locationH][locationW][0]){
            int check = checkInsertDirection(locationH, locationW, prevH, prevW);
            int nextH =0;
            int nextW =0;
            if(1 == check){
                nextH = locationH+1;
                nextW = locationW;
                direction = 2;
            }
            else if(2 == check){
                nextH = locationH;
                nextW = locationW - 1;
                direction = 1;
            }
            else if(3 == check){
                nextH = locationH-1;
                nextW = locationW;
                direction = 1;
            }
            else if(4 == check){
                nextH = locationH;
                nextW = locationW + 1;
                direction = 2;
            }
            if(nextH < 0){
                nextH = hSize-1;
            }
            else if(nextH == hSize){
                nextH = 0;
            }
            if(nextW < 0){
                nextW = wSize-1;
            }
            else if(nextW == wSize){
                nextW = 0;
            }
            prevH = locationH;
            prevW = locationW;
            locationH = nextH;
            locationW = nextW;
        }
        // L인 경우
        else if(2 == map[locationH][locationW][0]){
            int check = checkInsertDirection(locationH, locationW, prevH, prevW);
            int nextH =0;
            int nextW =0;
            if(1 == check){
                nextH = locationH;
                nextW = locationW+1;
                direction = 2;
            }
            else if(2 == check){
                nextH = locationH+1;
                nextW = locationW;
                direction = 2;
            }
            else if(3 == check){
                nextH = locationH;
                nextW = locationW-1;
                direction = 1;
            }
            else if(4 == check){
                nextH = locationH-1;
                nextW = locationW;
                direction = 1;
            }
            if(nextH < 0){
                nextH = hSize-1;
            }
            else if(nextH == hSize){
                nextH = 0;
            }
            if(nextW < 0){
                nextW = wSize-1;
            }
            else if(nextW == wSize){
                nextW = 0;
            }
            prevH = locationH;
            prevW = locationW;
            locationH = nextH;
            locationW = nextW;
        }
        // R인 경우
        else if(3 == map[locationH][locationW][0]){
            int check = checkInsertDirection(locationH, locationW, prevH, prevW);
            int nextH =0;
            int nextW =0;
            if(1 == check){
                nextH = locationH;
                nextW = locationW-1;
                direction = 1;
            }
            else if(2 == check){
                nextH = locationH-1;
                nextW = locationW;
                direction = 1;
            }
            else if(3 == check){
                nextH = locationH;
                nextW = locationW+1;
                direction = 2;
            }
            else if(4 == check){
                nextH = locationH+1;
                nextW = locationW;
                direction = 2;
            }
            if(nextH < 0){
                nextH = hSize-1;
            }
            else if(nextH == hSize){
                nextH = 0;
            }
            if(nextW < 0){
                nextW = wSize-1;
            }
            else if(nextW == wSize){
                nextW = 0;
            }
            prevH = locationH;
            prevW = locationW;
            locationH = nextH;
            locationW = nextW;
        }
    }    
    
    return count;
}



vector<int> solution(vector<string> grid) {
    vector<int> answer;
    
    hSize = (int)grid.size() *2 +1;
    wSize = (int)grid[0].size()*2 +1;
    
    makeMap(wSize, hSize, grid);
    
    for(int i=1; i < hSize; i+=2){
        for(int k=1; k < wSize; k+=2){
            for(int n =0; n < 4; n++){
                int goH = i + moveH[n];
                int goW = k + moveW[n];
                int direc = n %2 + 1; // 1 =상,좌, , 2=하,우
                if(1 == map[goH][goW][direc]){
                    continue;
                }                
                int count = cycle(direc, goH, goW, i, k);
                answer.push_back(count);
            }
        }
    }  
    sort(answer.begin(), answer.end());
    
    return answer;
    
}

꾸준히 하다보면 실력이 늘겠지..